package VaaneeDecode;

use List::Permutor;
use vaaneeConfig qw(%C);
use Varg qw(%C);
use DepTree qw(%C);
use Align qw(%C);
use Features qw(%dbs %C);  

use AlignBeam qw(%C);
use Parameters qw(%C);
use LocalBeam qw(%C);

use PQ qw();

@ISA = qw(Exporter);
@EXPORT = qw();
@EXPORT_OK = qw(%dbs %C);
$flag = "o";

sub new {
	my($corpus) = {};
	my($classname) = shift;
	bless($corpus);

	my($srcFile) = shift;
	my($tgtFile) = shift;
	my($srcDep) = shift;
	my($srcAlign) = shift;

	my($line);

	# Temporary variables
	my($a,$b,$c);

	my($sennum,$word,@words,@temparr,$tempsca);

	my($Varg,$Align,$AlignBeam,$StringBeam,$Features,$Dep);

	my(@tempalns);
	my($i,$j,$k);
	my($srcword,$tgtword);
	my(%sentencenums);
	
	if($srcFile) {
		print STDERR "Loading Sens $srcFile\n";
		$corpus->loadSen('SSen',$srcFile);
	}

	if($tgtFile) {
		print STDERR "Loading Tgt Sens $tgtFile\n";
		$corpus->loadSen('TSen',$tgtFile);
	}

	if($srcDep) {
		print STDERR "Loading Deps $srcDep\n";
		$corpus->loadDep('SDep',$srcDep,'SSen');
	}

	if($srcAlign) {
		print STDERR "Loading Aligns $srcAlign\n";
		$corpus->loadAlign('Align',$srcAlign);
	}

	# Add the gold features

#	Sriram Did this just now - 25 Feb , 4pm 2009
	if($srcAlign ne "")
	{
		print STDERR "Adding Gold Node Features\n";
		$corpus->addGoldnodeFeats('nodeFeatures');
#		$corpus->addGoldnodeLFeats('nodeLFeatures');
#		$corpus->addGoldnodeOFeats('nodeOFeatures');
#		$corpus->printGoldFeats();

#		$corpus->printHeadBasedStrings("headBasedStrings.txt");

#		print "Adding Gold Sentence Features\n";

#		$corpus->addGoldsenFeats('SFeatures');
	}
	
	return $corpus;
}

sub printLists {

	my($corpus) = shift;

	$corpus->printHeadBasedStrings("headBasedStrings.txt");
	$corpus->printSubTreeStrings("subTreeStrings.txt");
	$corpus->printRole2Vib("role2Vib.txt");
	$corpus->printTense2Tense("tense2Tense.txt");
	$corpus->printGnp2Gnp("gnp2Gnp.txt");
	$corpus->printAtomicTreelets("atomicTreelets.txt");
	
}

sub print {
	my $corpus = shift;
	foreach $senNum (sort {$a<=>$b} keys %$corpus) {
		my($engsen) = $corpus->{$senNum}->{'SSen'};
		my($hinsen) = $corpus->{$senNum}->{'TSen'};
		my($engDep) = $corpus->{$senNum}->{'SDep'};
		my($Align) = $corpus->{$senNum}->{'Align'};

		print $engsen." ".$hinsen." ".$engDep." ".$Align."\n";
	}
}

sub getDepthFirst {
	my($corpus) = shift;
	my($senNum) = shift;
	my($root) = shift;

	my(@depthFirst) = ();
	my(@candidates) = ($root);

	my($consider);
	while(@candidates) {
		$consider = shift(@candidates);
		push(@depthFirst,$consider);
		my(@children) = @{$corpus->{$senNum}->{'SDep'}->[$consider]->{'attch'}};
		push(@candidates,@children);
	}	
	return reverse @depthFirst;
}

sub addGoldnodeFeats {
	my $corpus = shift;
	my $type = shift;
	my $senNum ;
	my $i,$j;

	foreach $senNum (sort {$a<=>$b} keys %$corpus) {

		if($C{'senTrain'} < $senNum) {
			last;
		}

		print STDERR "Adding Gold node feats ($type) for Sentence: $senNum\n";

		local(%exclude);	
		if($corpus->{$senNum}->{'SDep'}->[0]->{'root'} eq "") {
			next;
		}

		my($TDep) = new DepTree;
		my($SDep) = $corpus->{$senNum}->{'SDep'};

		$corpus->getManySomeNodes($senNum,$SDep->[0]->{'root'});

		@depthFirstList = $corpus->getDepthFirst($senNum,$SDep->[0]->{'root'});;

		$nodeNum=0;
		my(%srcToTgtNodes) = ();

		foreach $i (@depthFirstList) {

			my(@alns) = @{$corpus->{$senNum}->{'Align'}->{'aln'}->[$i]};
			my($minAln) = $alns[0];
			my($maxAln) = $alns[$#alns];
			my($srcNode) = "NULL";
			my($tgtRoot,$tgtGNP,$tgtVib,$tgtTense);
			my($localString);

			if(!$exclude{$i}) {
				
 		     		($srcNode,$onlyChildren)=$corpus->getManySomeGold($senNum,$i);

				my($r,$g,$v,$t);

				foreach my $aln (@alns) {
					$tgtRoot.=$corpus->{$senNum}->{'TSen'}->[$aln]->{'root'}."_";

					$r=$corpus->{$senNum}->{'TSen'}->[$aln]->{'root'};
					$g=$corpus->{$senNum}->{'TSen'}->[$aln]->{'gnp'};
					$v=$corpus->{$senNum}->{'TSen'}->[$aln]->{'vib'};
					$t=$corpus->{$senNum}->{'TSen'}->[$aln]->{'tense'};

					#$localString.="$r+$v+$t+$g---";
					$localString.="$r---";
				}

				$localString=~s/---$//g;
				$localString.="+$v+$t+$g";
				$localString=$corpus->{$senNum}->{'SSen'}->[$i]->{'pos'}."[".$localString."]";

				$tgtGNP.=$corpus->{$senNum}->{'TSen'}->[$maxAln]->{'gnp'}."_";
				$tgtVib.=$corpus->{$senNum}->{'TSen'}->[$maxAln]->{'vib'}."_";
				$tgtTense.=$corpus->{$senNum}->{'TSen'}->[$maxAln]->{'tense'}."_";

				$tgtRoot=~s/.$//g; $tgtGNP=~s/.$//g; $tgtVib=~s/.$//g; $tgtTense=~s/.$//g;

			}
			else {
				($tgtRoot,$tgtGNP,$tgtVib,$tgtTense) = ("NULL","NULL","NULL","NULL");
				$localString = "";
			}
			
		#	print STDERR $srcNode."\t".$onlyChildren."\t".eval(@{$onlyChildren})."\n";
#			print STDERR "$tgtRoot $tgtGNP $tgtVib $tgtTense\n";
			

			$srcToTgtNodes{$i} = $nodeNum;
			$TDep->createnode($nodeNum);

			$TDep->addFac($nodeNum,"rt",$tgtRoot);
			$TDep->addFac($nodeNum,"gnp",$tgtGNP);
			$TDep->addFac($nodeNum,"vib",$tgtVib);
			$TDep->addFac($nodeNum,"tense",$tgtTense);
			$TDep->addFac($nodeNum,"minPos",$minAln);
			$TDep->addFac($nodeNum,"maxPos",$maxAln);
			$TDep->addFac($nodeNum,"srcRole",$SDep->[$i]->{'role'});
			$TDep->addFac($nodeNum,"srcPos",$corpus->{$senNum}->{'SSen'}->[$i]->{'pos'});
			$TDep->addFac($nodeNum,"localString",$localString);

			my($child);
			my(%posChild);
			foreach $child (@{$onlyChildren}) {
				$posChild{$child} = $TDep->[$srcToTgtNodes{$child}]->{'minPos'};
			}
			my($childPosition,$rootPosition,%relPosChild);
			my($subTreeString) = "";
			my($headsString) = "";
			$childPosition=0;
			$rootPosition=-1;
			foreach $child (sort {$posChild{$a}<=>$posChild{$b}} keys %posChild) {
				if($posChild{$child}>$minAln) {
					$rootPosition=$childPosition;
					$childPosition++;
					$subTreeString.=$localString."___" if($localString);
					$headsString.=$localString."&___" if($localString);
				}	
				$relPosChild{$child} = $childPosition;
				$childPosition++;
				my $s;
				$s=$TDep->[$srcToTgtNodes{$child}]->{'subTreeString'};
				$s=~s/\]\&/\]/g;
				$subTreeString.=$s."___" if($s);
				$s=$TDep->[$srcToTgtNodes{$child}]->{'localString'};
				$headsString.=$s."___" if($s);
			}

			if($rootPosition==-1) {
				$rootPosition=$childPosition;
				$subTreeString.=$localString."___" if($localString);
				$headsString.=$localString."&___" if($localString);
			}

			foreach $child (sort {$posChild{$a}<=>$posChild{$b}} keys %posChild) {
				$relPosChild{$child} = $relPosChild{$child}-$rootPosition;
			}

			foreach $child (@{$onlyChildren}) {
#				print STDERR "Adding $srcToTgtNodes{$child}(or $child) to $nodeNum\n";
				$TDep->addattch($nodeNum,$srcToTgtNodes{$child});
				$TDep->addFac($srcToTgtNodes{$child},"relPos",$relPosChild{$child});
			}

			$SDep->addFac($i,"srcNode",$srcNode);
			$SDep->addFac($i,"align",$nodeNum);
		
			$subTreeString=~s/___$//g;
			$headsString=~s/___$//g;
			$TDep->addFac($nodeNum,"subTreeString",$subTreeString);
			$TDep->addFac($nodeNum,"headsString",$headsString);
			
			my $Features;


			$Features = new Features;

			#print STDERR "Adding Gold Features : $senNum==$i($srcNode,$nodeNum)\n";
			if(!$exclude{$i}) {
			$Features->getnodeTransFeats($srcNode,$nodeNum,$corpus->{$senNum}->{'SSen'},$SDep,$TDep,$onlyChildren,"u");
#			$Features->getnodeFeaturesNew($srcNode,$corpus->{$senNum}->{'SSen'},$corpus->{$senNum}->{'TSen'},
#						      $corpus->{$senNum}->{'SDep'},$corpus->{$senNum}->{'Align'},"u",
#						      $onlyChildren);

#			print STDERR "Printing Features $senNum $type $i $Features\n";
#			$Features->print();
#			print STDERR "\n";
			}

			$corpus->{$senNum}->{$type}->[$i] = $Features;
			$nodeNum++;

#			$TDep->printTree();
		}
		$TDep->[0]->{'root'} = $srcToTgtNodes{$corpus->{$senNum}->{'SDep'}->[0]->{'root'}};
		$corpus->{$senNum}->{'TDep'} = $TDep;
	}

	return $corpus;
}

sub addGoldnodeLFeats {
	my $corpus = shift;
	my $type = shift;
	my $senNum ;
	my $i,$j;

	foreach $senNum (sort {$a<=>$b} keys %$corpus) {
#		print STDERR "Adding Gold Local node feats ($type) for Sentence: $senNum\n";
#		print "Adding Gold Local node feats ($type) for Sentence: $senNum\n";
		if($C{'senTrain'} < $senNum) {
			last;
		}

		for($i=0;$i<@{$corpus->{$senNum}->{'SSen'}};$i++) {

			my $Features;

			$Features = new Features;
			$Features->getnodeLFeatures($i,$corpus->{$senNum}->{'SSen'},$corpus->{$senNum}->{'TSen'},
						      $corpus->{$senNum}->{'Align'}->{'aln'}->[$i],"u");

			$corpus->{$senNum}->{$type}->[$i] = $Features;
#			print "$i)\n";
#			$Features->print();
		}
	}

	return $corpus;
}

sub addGoldnodeOFeats {
	my $corpus = shift;
	my $type = shift;
	my $senNum ;
	my $i,$j;

	foreach $senNum (sort {$a<=>$b} keys %$corpus) {
		print STDERR "Adding Gold node feats for Sentence: $senNum\n";
		#print "Adding Gold node Other feats for Sentence: $senNum\n";
		if($C{'senTrain'} < $senNum) {
			last;
		}

		for($i=0;$i<@{$corpus->{$senNum}->{'SSen'}};$i++) {

			my $Features;

			$Features = new Features;
			$Features->getnodeOFeatures($i,$corpus->{$senNum}->{'SSen'},$corpus->{$senNum}->{'TSen'},
						      $corpus->{$senNum}->{'SDep'},$corpus->{$senNum}->{'Align'},"u");

			$corpus->{$senNum}->{$type}->[$i] = $Features;
#			print "FEATURES FOR sentence : $senNum, Node : $i\n";
#			$Features->print();

		}
	}

	return $corpus;
}

sub printGoldFeats {
	my $corpus = shift;
	my $senNum ;
	my $i,$j;

	foreach $senNum (sort {$a<=>$b} keys %$corpus) {
		if($C{'senTrain'} < $senNum) {
			last;
		}

		print STDERR "print All Features for Sentence: $senNum\n";
		print "Print All Features for Sentence: $senNum\n";
		for($i=0;$i<@{$corpus->{$senNum}->{'SSen'}};$i++) {

			my $Features;

			print STDERR "$senNum) Node $i\n";

			$corpus->{$senNum}->{'nodeFeatures'}->[$i]->print() if($corpus->{$senNum}->{'nodeFeatures'});
#			$corpus->{$senNum}->{'nodeLFeatures'}->[$i]->print();
#			$corpus->{$senNum}->{'nodeOFeatures'}->[$i]->print();
#			print "Node $i ($senNum $type $i)\n";
		}
	}

	return $corpus;
}

sub printSubTreeStrings {
	my $corpus = shift;
	my $fileName = shift;
	my $senNum ;
	my $i,$j;

	open(FILE,">$fileName");

	foreach $senNum (sort {$a<=>$b} keys %$corpus) {
		if($C{'senTrain'} < $senNum) {
			last;
		}

		my $TDep = $corpus->{$senNum}->{'TDep'};
		for($i=0;$i<=$#$TDep;$i++) {
			$string=$TDep->[$i]->{'subTreeString'};
			print FILE $TDep->[$i]->{'srcPos'}."\t".$string."\n" if($string);
		}
	}
	close(FILE);
}

sub printHeadBasedStrings {
	my $corpus = shift;
	my $fileName = shift;
	my $senNum ;
	my $i,$j;

	open(FILE,">$fileName");

	foreach $senNum (sort {$a<=>$b} keys %$corpus) {
		if($C{'senTrain'} < $senNum) {
			last;
		}

		my $TDep = $corpus->{$senNum}->{'TDep'};
		for($i=0;$i<=$#$TDep;$i++) {
			$string=$TDep->[$i]->{'headsString'};
			print FILE $TDep->[$i]->{'srcPos'}."\t".$string."\n" if($string);
		}
	}
	close(FILE);
}

sub printRole2Vib {
	my $corpus = shift;
	my $fileName = shift;
	my $senNum ;
	my $i,$j;

	open(FILE,">$fileName");

	foreach $senNum (sort {$a<=>$b} keys %$corpus) {
		if($C{'senTrain'} < $senNum) {
			last;
		}

		my $TDep = $corpus->{$senNum}->{'TDep'};
		for($i=0;$i<=$#$TDep;$i++) {
			my($role) = $TDep->[$i]->{'srcRole'};
			$role="ROOT" if(! $role);
			print FILE $role."\t".$TDep->[$i]->{'vib'}."\n";
		}
	}
	close(FILE);
}

sub printTense2Tense {
	my $corpus = shift;
	my $fileName = shift;
	my $senNum ;
	my $i,$j;

	open(FILE,">$fileName");

	foreach $senNum (sort {$a<=>$b} keys %$corpus) {
		if($C{'senTrain'} < $senNum) {
			last;
		}

		my $SDep = $corpus->{$senNum}->{'SDep'};
		my $engsen = $corpus->{$senNum}->{'SSen'};
		my $hinsen = $corpus->{$senNum}->{'TDep'};

		for($i=0;$i<=$#$SDep;$i++) {
			my($srcTense) = $engsen->[$i]->{'tense'};
			my($tword) = $SDep->[$i]->{'align'};
			my($tgtWord) = $hinsen->[$i]->{'root'};
			my($tgtTense) = $hinsen->[$tword]->{'tense'};

			if($tgtWord ne "NULL" && $srcTense) {
				print FILE $srcTense."\t".$tgtTense."\n";
			}
		}
	}
	close(FILE);
}

sub printGnp2Gnp {
	my $corpus = shift;
	my $fileName = shift;
	my $senNum ;
	my $i,$j;

	open(FILE,">$fileName");

	foreach $senNum (sort {$a<=>$b} keys %$corpus) {
		if($C{'senTrain'} < $senNum) {
			last;
		}

		my $SDep = $corpus->{$senNum}->{'SDep'};
		my $engsen = $corpus->{$senNum}->{'SSen'};
		my $hinsen = $corpus->{$senNum}->{'TDep'};

		for($i=0;$i<=$#$SDep;$i++) {
			my($srcGnp) = $engsen->[$i]->{'gnp'};
			my($tword) = $SDep->[$i]->{'align'};
			my($tgtWord) = $hinsen->[$i]->{'root'};
			my($tgtGnp) = $hinsen->[$tword]->{'gnp'};

			if($tgtWord ne "NULL") {
				print FILE $srcGnp."\t".$tgtGnp."\n";
			}
		}
	}
	close(FILE);
}

sub printAtomicTreelets {
	my $corpus = shift;
	my $fileName = shift;
	my $senNum ;
	my $i,$j;

	open(FILE,">$fileName");

	foreach $senNum (sort {$a<=>$b} keys %$corpus) {
		if($C{'senTrain'} < $senNum) {
			last;
		}

		my $SDep = $corpus->{$senNum}->{'SDep'};
		my $TDep = $corpus->{$senNum}->{'TDep'};
		my $engsen = $corpus->{$senNum}->{'SSen'};
		my $hinsen = $corpus->{$senNum}->{'TDep'};

		for($i=0;$i<=$#$SDep;$i++) {
			$srcNode = $SDep->[$i]->{'srcNode'};
			$tword = $SDep->[$i]->{'align'};
			$tRoot = $TDep->[$tword]->{'rt'};

			if($srcNode ne "NULL" && $tRoot) {
				my($srcNodeWordPos)="";
				while($srcNode=~/(l[0-9]+)~([0-9]+)/g) {
					my($sword) = $engsen->[$2]->{'root'};
					my($spos) = $engsen->[$2]->{'pos'};
					$srcNodeWordPos.=$1."~".$sword."~".$spos."___";
				}
				
				$srcNodeWordPos=~s/___$//g;
				print FILE $srcNodeWordPos."\t".$tRoot."\n";
			}
		}
		print FILE "=========================\n";
	}
	close(FILE);
}


sub addGoldsenFeats {
	my $corpus = shift;
	my $type = shift;
	my($Parameters) = shift;
	my $senNum ;
	my $i,$j;

	foreach $senNum (sort {$a<=>$b} keys %$corpus) {

		my $Features;
		if($C{'senTrain'} < $senNum) {
			last;
		}


# print STDERR "Adding gold node feats for Sentence: $senNum\n";

		$Features = new Features;
		$Features->getsenFeatures($corpus->{$senNum}->{'SSen'},$corpus->{$senNum}->{'TSen'},
				$corpus->{$senNum}->{'SDep'},$corpus->{$senNum}->{'Align'},"u");

		$corpus->{$senNum}->{$type} = $Features;

#print "Adding SEN Feats of $senNum\n";
#$Features->print();

	}

	return $corpus;
}

sub loadDictionary {
	my($dictFile) = shift;
	my(%dict) ;

	open(DICT,"$dictFile") || die "Couldn't open $dictFile\n";

	while($entry=<DICT>) {
		chomp($entry);
		($srcWord,$tgtWord,$score) = split(/\s+/,$entry);
		$dict{"$srcWord"}->{"$tgtWord"} = $score;
	}
	
	close(DICT);
	return \%dict;
}

sub loadSen {

	my($corpus) = shift;
	my($type) = shift;
	my($file) = shift;

	open(FILE,$file) || die "Could not open $file\n";

	my @lines = <FILE>;
	chomp(@lines);

	my $no_lines = @lines;
	my $senNum ;
	my $i=0;
	my $wordnum = 0;
	my $flag = "i";

	$senStart=1;
#	$senNum=1;
	if($flag eq "i")
	{
		for($i=0; $i < $no_lines; $i++)
		{
			if($lines[$i] =~ /^\s*$/)
			{
				$senStart=1;
			#	$wordnum=0;
			#	$senNum++;
			}
	#	Change made by Sriram  Feb 26, 2009
			elsif($senStart==1 && $lines[$i] =~ /^([0-9]+)$/)
			{
				$senNum = $1;
				$wordnum = 0;
				$senStart=0;
			}
			else
			{
				my($word_POS_root,@features) = split(/\t/,$lines[$i]);

				my($word,$pos,$root) = split(/_/,$word_POS_root);
#print "$senNum $type $word $pos $root\n";

				$corpus->{$senNum}->{$type}->[$wordnum]->{'word'} = $word;
				$corpus->{$senNum}->{$type}->[$wordnum]->{'pos'} = $pos;
				$corpus->{$senNum}->{$type}->[$wordnum]->{'root'} = $root;

# For 'prep' and 'aux' of the word. 

				my $feature;
				foreach $feature (@features)
				{
					my ($feat,$value) = split(/:/,$feature); 
					$corpus->{$senNum}->{$type}->[$wordnum]->{$feat} = $value;
				}
				$wordnum++;
			}
		}
	}
	else
	{
		for($i=0; $i < $no_lines; $i++)
		{
#                       print $lines[$i]."\n";
			$senNum = $i + 1;
			$wordnum = 0;
			@words = split(/\s+/,$lines[$i]);
			foreach $word_POS_root (@words)
			{
				my($word,$pos,$root) = split(/_/,$word_POS_root);
				$corpus->{$senNum}->{$type}->[$wordnum]->{'word'} = $word;
				$corpus->{$senNum}->{$type}->[$wordnum]->{'pos'} = $pos;
				$corpus->{$senNum}->{$type}->[$wordnum]->{'root'} = $root;

				$wordnum++;
			}
		}

	}
}

sub loadDep {

	my($corpus) = shift;
	my($type) = shift;
	my($depfname) = shift;
	my($type2) = shift;
	my($senNum);
	
	open(DEPTREE,$depfname) || die "Can't open deptree = $depfname\n";
	my($depline);
	my($procsen) = 0;
	my($senidx,$rootpos) ;
	my($Senid) = 1;

	while($depline=<DEPTREE>)
	{
		chomp($depline);
#		SRIRAM CHANGE Aug 07, 2008
		$senNum = eval($depline);

		my($Dep) = new DepTree;

		my $line = <DEPTREE>;
		chomp($line);
		($temp,$root_pos) = split(/\s+/,$line);

		$Dep->addroot($root_pos);

		while(!($line=~/^\s*$/))
		{
			$line = <DEPTREE>; chomp($line);

			if($line=~/^[#](.*?) (.*)$/)
			{
				$word_num = $1;
				$Dep->createnode($word_num);
				$Dep->addFac($word_num,'word',$2);

				$line = <DEPTREE>;  chomp($line);
			}
			elsif($line=~/pos: (.*)/) {
				$Dep->addpos($word_num,$1);
			}
			elsif($line=~/role: (.*)/) {
				$Dep->addrole($word_num,$1);
			}

			elsif($line=~/att #(.*)/)
			{
				$Dep->addattch($word_num,$1);
			}
			if($line=~/^[&](.*?)$/)   #Ask Karthik to check this
			{
				$word_num = $1;

				$line = <DEPTREE>;  chomp($line);

				$Dep->createnode($word_num);
				$corpus->{$senNum}->{$type2}->[$word_num]->{'word'} = "DUMMY";
				$corpus->{$senNum}->{$type2}->[$word_num]->{'pos'} = "DUMMY";
				$corpus->{$senNum}->{$type2}->[$word_num]->{'root'} = "DUMMY";
			}
			elsif($line=~/con #(.*)/)
			{
				$Dep->addattch($word_num,$1);
			}
		}

		# Add Parent Information
		for($i=0;$i<$#$Dep;$i++) {
			foreach $attch (@{$Dep->[$i]->{'attch'}}) {
				$Dep->addFac($attch,'parent',$i);	
			}
		}	

		$corpus->{$senNum}->{$type} = $Dep;
	}
}

sub loadAlign {
	my($corpus) = shift;
	my($type) = shift;
	my($file) = shift;
	my($strength) = shift;

	open(FILE,$file) || die "Can't open align = $file\n";
	my @lines = <FILE>;

	my($line);
	my $no_lines = @lines;
	my $senNum;
	my $i=0;
	my $wordnum = 0;
	my $alignments;
	
	for($i=0; $i < $no_lines; $i++)
	{
		$line = $lines[$i]; 
		($senNum,$srcword,$tgtword,$strength) = split(/\s+/,$line);
		if($strength==0) {
			$alignments->{$senNum}->{"$srcword $tgtword"} = 1;
		}

	}

	foreach $senNum (keys %{$alignments}) {
		my $Align = new Align;

		foreach $line (keys %{$alignments->{$senNum}}) {
			($srcword,$tgtword) = split(/\s+/,$line);
			$Align->addalign($srcword,$tgtword);
		}

		$corpus->{$senNum}->{$type} = $Align; 

	}
}

sub predictAndupdate2 {

	my($corpus) = shift;
	my($senNum) = shift;
	my($Parameters) = shift;
	my($ifUpdate) = shift;
	my($i);

	my($Varg,$Dep);
	my($engsen,$hinsen);
	my($GoldAlign,$GenAlign,$GenAlign2);
	my($Beam,$TempBeam);
	my($LFeatures,$score);
	my($localbeam,%localbeams);
	my($k,$m,$n,$p,$i);
	my($minScore,$minPosition);
	my($hinwordpos);
	my($verbnum,$argnum);
	my($LFeatures,$GenFeatures);
	my($nengwords,$nhinwords);

	
	$Dep = $corpus->{$senNum}->{'SDep'};
	$engsen = $corpus->{$senNum}->{'SSen'};
	$nengwords = @{$engsen};
	$hinsen = $corpus->{$senNum}->{'TSen'};
	$nhinwords = @{$hinsen};
	$GoldAlign = $corpus->{$senNum}->{'Align'};


	$corpus->{$senNum}->{'AlignBeam'} = new AlignBeam($C{'K'});
	$Beam = $corpus->{$senNum}->{'AlignBeam'};

	my($s);

#	print STDERR "$senNum) words($nengwords):".scalar($nhinwords);
#	print STDERR "words($nengwords):".scalar($nhinwords)."\n\n";
	$starttime = time();

	my($obj,$priorIty);

#	$GoldAlign->printAln($engsen,$hinsen);
	$corpus->predictAndupdatenode($senNum,$Dep->[0]->{'root'},$Parameters,$ifUpdate);

}

sub predictAndupdate3 {

	my($corpus) = shift;
	my($senNum) = shift;
	my($Parameters) = shift;
	my($ifUpdate) = shift;
	my($i);

	my($Varg,$Dep);
	my($engsen,$hinsen);
	my($GoldAlign,$GenAlign,$GenAlign2);
	my($Beam,$TempBeam);
	my($LFeatures,$score);
	my($localbeam,%localbeams);
	my($k,$m,$n,$p,$i);
	my($minScore,$minPosition);
	my($hinwordpos);
	my($verbnum,$argnum);
	my($LFeatures,$GenFeatures);
	my($nengwords,$nhinwords);

	
	$Dep = $corpus->{$senNum}->{'SDep'};
	$engsen = $corpus->{$senNum}->{'SSen'};
	$nengwords = @{$engsen};
	$hinsen = $corpus->{$senNum}->{'TSen'};
	$nhinwords = @{$hinsen};
	$GoldAlign = $corpus->{$senNum}->{'Align'};


	$corpus->{$senNum}->{'AlignBeam'} = new AlignBeam($C{'K'});
	$Beam = $corpus->{$senNum}->{'AlignBeam'};

	my($s);

#	print STDERR "$senNum) words($nengwords):".scalar($nhinwords);
#	print STDERR "words($nengwords):".scalar($nhinwords)."\n\n";
	$starttime = time();

	my($obj,$priorIty);

#	$GoldAlign->printAln($engsen,$hinsen);
	$corpus->predictAndupdatenode2($senNum,$Dep->[0]->{'root'},$Parameters,$ifUpdate);

}

sub trainAlgo4{

	my($corpus) = shift;
	my($senNum) = shift;
	my($Parameters) = shift;
	my($ifUpdate) = shift;

	local(%subTreeAligns);
	local(%exclude);
	local(%tgtAlnDone);
	my($Dep);
	local($MAXITER) = $C{'maxTrainIter'};
	
	$Dep = $corpus->{$senNum}->{'SDep'};

	print "Training Sentence $senNum\n";

	$corpus->getManySomeNodes($senNum,$Dep->[0]->{'root'});
	
	$corpus->trainNode($senNum,$Dep->[0]->{'root'},$Parameters);

	print "-------------------------------\n";

}

sub trainAlgo5{

	my($corpus) = shift;
	my($senNum) = shift;
	my($Parameters) = shift;
	my($ifUpdate) = shift;

	local(%subTreeTrans);
	local(%exclude);
	local(%tgtAlnDone);
	my($SDep,$TDep);
	local($MAXITER) = $C{'maxTrainIter'};
	
	$SDep = $corpus->{$senNum}->{'SDep'};
	$TDep = $corpus->{$senNum}->{'TDep'};

	print STDERR "xTraining Sentence $senNum\n";
#	print STDERR "Print Source-Target Dependency Trees\n";
#	$SDep->printTree();
#	$TDep->printTree();

	$corpus->getManySomeNodes($senNum,$SDep->[0]->{'root'});
	
	$corpus->trainNodeDecode($senNum,$SDep->[0]->{'root'},$Parameters);

#	print STDERR "x-------------------------------\n";

}

sub decodeBottomUp{

	my($corpus) = shift;
	my($senNum) = shift;
	my($Parameters) = shift;
	my($ifUpdate) = shift;

	local(%subTreeTrans);
	local(%exclude);
	local(%tgtAlnDone);
	my($SDep,$TDep);
	local($MAXITER) = $C{'maxTrainIter'};
	
	$SDep = $corpus->{$senNum}->{'SDep'};

	print STDERR "Decoding Sentence $senNum\n";
#	print STDERR "Print Source-Target Dependency Trees\n";
#	$SDep->printTree();
#	$TDep->printTree();

	$corpus->decodeNode($senNum,$SDep->[0]->{'root'},$Parameters);

	my($FinalTDep) = $subTreeTrans{$SDep->[0]->{'root'}}->{'tTree'};
	$FinalTDep->printTree();
	my($subTreeString) = $FinalTDep->[$FinalTDep->[0]->{'root'}]->{'subTreeString'};
	$subTreeString=~s/\_\_\_/ /g;
	$subTreeString=~s/[^\[\s]+\[(.*?)\]/$1/g;
	$subTreeString=~s/---/ /g;
	print $subTreeString."\n";

	#$Beam->[0]->{'tTree'}->printTree();
	#$Beam->[0]->{'nodeFeats'}->print();

#	print STDERR "x-------------------------------\n";

}


sub decode {

	my($corpus) = shift;
	my($senNum) = shift;
	my($Parameters) = shift;
	my($ifUpdate) = shift;

	local(%subTreeTrans);
	local(%exclude);
	local(%tgtAlnDone);
	my($SDep,$TDep);
	local($MAXITER) = $C{'maxTrainIter'};
	
	$SDep = $corpus->{$senNum}->{'SDep'};
	$TDep = $corpus->{$senNum}->{'TDep'};

	print STDERR "xTraining Sentence $senNum\n";
#	print STDERR "Print Source-Target Dependency Trees\n";
#	$SDep->printTree();
#	$TDep->printTree();

	$corpus->getManySomeNodes($senNum,$SDep->[0]->{'root'});
	
	$corpus->trainNodeDecode($senNum,$SDep->[0]->{'root'},$Parameters);

#	print STDERR "x-------------------------------\n";

}




sub testAlgo4 {

	my($corpus) = shift;
	my($senNum) = shift;
	my($Parameters) = shift;
	my($ifUpdate) = shift;
	local(%subTreeAligns);
	local(%localAln);
	local(%rootManySome);
	my($Dep);
	
	$Dep = $corpus->{$senNum}->{'SDep'};

	$corpus->testNode($senNum,$Dep->[0]->{'root'},$Parameters);

	foreach $comp (sort {$a<=>$b} keys %subTreeAligns) {
		my $alnPt;
		foreach $alnPt (@{$subTreeAligns{$comp}->{'alnPts'}}) {
			print "$senNum\t$comp\t$alnPt\n";
			print STDERR "$senNum\t$comp\t$alnPt\n";
		}
	}

}

sub testAlgo5 {

	my($corpus) = shift;
	my($senNum) = shift;
	my($Parameters) = shift;
	my($ifUpdate) = shift;
	my($rootNode);
	local(%subTreeAligns);
	my($Dep);
	
	$Dep = $corpus->{$senNum}->{'SDep'};
	$engsen = $corpus->{$senNum}->{'SSen'};
	$rootNode = $Dep->[0]->{'root'};

	$corpus->testNode2($senNum,$rootNode,$Parameters);

	my($bestAlign) = $subTreeAligns{$rootNode}->[0]->{'align'};
#	$bestAlign->print($engsen);
	$bestAlign->printEval($senNum);
#	foreach $item (@$Beam) {
#		print "Prediction $predNum\n";
#		print "SrcNode = $item->{'srcNode'}\n";
#		print "Local Score = ".$item->{'localScore'}."\n";
#		$item->{'align'}->print($engsen);
#		$item->{'nodeFeats'}->print();
#		$predNum++;
#	}
#	print "--------\n";

}


sub getManySomeNodes {

	my($corpus,$senNum,$root) = ($_[0],$_[1],$_[2]);
	my($manyMany) = {};
	my($senCorpus) = $corpus->{$senNum};


	my @rootAlns = @{$senCorpus->{'Align'}->{'aln'}->[$root]};

	if(!defined $exclude{$root}) {

		local(%allAlns) = ();
		foreach my $aln (@rootAlns) {
			$allAlns{$aln} = 1;
		}

		for($word=0;$word<@{$senCorpus->{'SSen'}};$word++) {
			my @myAlns = @{$senCorpus->{'Align'}->{'aln'}->[$word]};
			if(&matchArr(\@rootAlns,\@myAlns) && $root!=$word) {
				foreach my $aln (@myAlns) {
					$allAlns{$aln} = 1;
				}
				$manyMany->{$word} = 1;
			}
		}

		my(@allAlnsArray) = keys %allAlns;
		@{$senCorpus->{'Align'}->{'aln'}->[$root]} = sort {$a<=>$b} @allAlnsArray;
		
		foreach $word (keys %$manyMany) {
			$exclude{$word} = 1;
		}

	}

	foreach $child (@{$senCorpus->{'SDep'}->[$root]->{'attch'}}) {
		$corpus->getManySomeNodes($senNum,$child);
	}
}


sub matchArr {
	my($arr1,$arr2) = ($_[0],$_[1]);

	if(@$arr1==0 || @$arr2==0) {
		return 0;
	}

	foreach $elem1 (@$arr1) {
		foreach $elem2 (@$arr2) {
			if($elem1==$elem2) {
				return 1;
			}
		}
	}
	return 0;
}

sub hasManySomeNodes {
	my($srcNode) = shift;
	my($flag) = 0;
	my(@tempNodes) = ();
	while($srcNode=~/l([0-9]+)~([0-9]+)/g) {
		if($rootManySome{$2}) {
			$flag = 1;
			last;
		}
	}
	return $flag;
}
				

sub testNode {
	
	my($corpus) = shift;
	my($senNum) = shift;
	my($rootNode) = shift;
	my($Parameters) = shift;
	my($Beam);

	my($Dep,$Align);
	
	$Dep = $corpus->{$senNum}->{'SDep'};

	my($child);
	foreach $child (@{$Dep->[$rootNode]->{'attch'}}) {
		$corpus->testNode($senNum,$child,$Parameters);
	}


#	print "Testing $senNum $rootNode\n";

	my(@srcNodes) = $corpus->getSrcNodes($senNum,$rootNode,0);
	my(@secondNodes) = $corpus->getSecondSrcNodes($senNum,\@srcNodes,$rootNode);
	push(@srcNodes,@secondNodes);
	my(@thirdNodes) = $corpus->getThirdSrcNodes($senNum,\@secondNodes,$rootNode);
	push(@srcNodes,@thirdNodes);

	# Make sure that Src Nodes do not have nodes that are part of many-some alignments already
	my($srcNode,@tempNodes);
	foreach $srcNode (@srcNodes) {
		if(! &hasManySomeNodes($srcNode)) {	
			push(@tempNodes,$srcNode);
		}
	}
	@srcNodes = @tempNodes;
	@oneNodes = ("l0~$rootNode");

#	print STDERR "Source Nodes = ".join(' , ',@srcNodes)."\n";
#	print "Root Node = ".join(' ',@oneNodes)."\n";

	$Beam = &getKBestAligns($corpus,$senNum,$rootNode,\@srcNodes,$Parameters,$C{'K'});
	$BeamIsolated = &getKBestAligns($corpus,$senNum,$rootNode,\@oneNodes,$Parameters,$C{'K'});

	my($localScores);
	$localAln{$rootNode} = $BeamIsolated->[0];

#	print "Local [$localAln{$rootNode}->{'srcNode'},".join('_',@{$localAln{$rootNode}->{'alnPts'}})."]\t";
#	print "Global [$Beam->[0]->{'srcNode'},".join('_',@{$Beam->[0]->{'alnPts'}})."]\n";

	# Compute Local Scores
	my($localScore) = 0;
	my($totalNodes) = 0;
	foreach $node (keys %{$Beam->[0]->{'srcPts'}}) {
		$localScore+=$Parameters->getScore($localAln{$node}->{'nodeFeats'});
		$totalNodes++;
	}
	$localScore/=$totalNodes;

	my($globalScore) = $Parameters->getScore($Beam->[0]->{'nodeFeats'});

	if($globalScore>$localScore) {
		print STDERR "HELLO Global $globalScore $localScore\n";
		foreach $node (keys %{$Beam->[0]->{'srcPts'}}) {
			$subTreeAligns{$node} = $Beam->[0];
		}
	}
	else {
		print STDERR "HELLO Local [$localAln{$rootNode}->{'srcNode'},".join('_',@{$localAln{$rootNode}->{'alnPts'}})."]\t";
		$subTreeAligns{$rootNode} = $localAln{$rootNode};
	}

	if($localAln{$rootNode}->{'srcNode'}  ne $Beam->[0]->{'srcNode'}) {
		print STDERR "Local [$localAln{$rootNode}->{'srcNode'},".join('_',@{$localAln{$rootNode}->{'alnPts'}})."]\t";
		foreach $node (keys %{$Beam->[0]->{'srcPts'}}) {
			print STDERR "  LS of $node = ".$Parameters->getScore($localAln{$node}->{'nodeFeats'})."\n";
		}
		print STDERR "Local Score = $localScore ($totalNodes nodes)\n";
		print STDERR "Global [$Beam->[0]->{'srcNode'},".join('_',@{$Beam->[0]->{'alnPts'}})."]\n";
		print STDERR "Global Score = $globalScore\n\n";
	}
	
	

}


sub trainNode {
	
	my($corpus) = shift;
	my($senNum) = shift;
	my($rootNode) = shift;
	my($Parameters) = shift;
	my($Beam,$node);

	my($Dep,$Align);
	
	$Dep = $corpus->{$senNum}->{'SDep'};
	$GoldAlign = $corpus->{$senNum}->{'Align'};

	my($child);
	foreach $child (@{$Dep->[$rootNode]->{'attch'}}) {
		$corpus->trainNode($senNum,$child,$Parameters);
	}


	print "TRAIN NODE $rootNode , ";
	print " GOLD =>".join('~',@{$GoldAlign->{'aln'}->[$rootNode]})." , "; 
	if(! $exclude{$rootNode}) {
	
#		print "\n";

		my(@srcNodes) = $corpus->getSrcNodes($senNum,$rootNode,0);
		my(@secondNodes) = $corpus->getSecondSrcNodes($senNum,\@srcNodes,$rootNode);
		push(@srcNodes,@secondNodes);
		my(@thirdNodes) = $corpus->getThirdSrcNodes($senNum,\@secondNodes,$rootNode);
		push(@srcNodes,@thirdNodes);

#		print " - - - GOLD FEATURES - - - $rootNode-\n";
#		$corpus->{$senNum}->{'nodeFeatures'}->[$rootNode]->print();
#		print " - - - - - - - - - - - - -\n";

		$Beam = &getKBestAligns($corpus,$senNum,$rootNode,\@srcNodes,$Parameters,$C{'K'});
#		foreach $node (keys %{$Beam->[0]->{'srcPts'}}) {
#			$subTreeAligns{$node} = $Beam->[0];
#		}


		my($iter) = 0;
		while($iter<$MAXITER && &getMistakesNew($rootNode,$Beam->[0],$GoldAlign,$Dep)) {

			my $i;
			my $PredFeatArray = [];
			my $mistakeArray = [];
=cut
			print "*****Updating Parameters****************\n";
			print " ---  GOLD --- $rootNode (of $senNum)--- ".join('~',@{$GoldAlign->{'aln'}->[$rootNode]})."\n";
			$corpus->{$senNum}->{'nodeFeatures'}->[$rootNode]->print();
			print "Score = ".$Parameters->getScore($corpus->{$senNum}->{'nodeFeatures'}->[$rootNode])."\n";
			print " - - - PREDICTIONS - - - -\n";
=cut
			for($i=0;$i<@{$Beam};$i++) {
				$PredFeatArray->[$i] = $Beam->[$i]->{'nodeFeats'};
				$mistakeArray->[$i] = &getMistakesNew($rootNode,$Beam->[$i],$GoldAlign,$Dep);
=cut				print "Prediction $i ($Beam->[$i]->{'srcNode'})=>".join('+',@{$Beam->[$i]->{'alnPts'}})." \n";
				$PredFeatArray->[$i]->print();
				print "Score = ".$Parameters->getScore($PredFeatArray->[$i])."\n";
				print "Left = $Beam->[$i]->{'leftPt'} , Right = $Beam->[$i]->{'rightPt'}\n";
				print "Nodes = $Beam->[$i]->{'nodesChildren'} $Beam->[$i]->{'tgtNodes'}\n";
				print "Mistakes = $mistakeArray->[$i]\n";
				print "- - - - - - - -\n";
=cut
			}

			$newK = scalar(@{$Beam});

			$Parameters->updateParams($corpus->{$senNum}->{'nodeFeatures'}->[$rootNode],$PredFeatArray,$mistakeArray,$newK);

			$Beam = &getKBestAligns($corpus,$senNum,$rootNode,\@srcNodes,$Parameters,$C{'K'});

			$iter++;
		}

		if($MAXITER==0 || $iter==$MAXITER) {
			my @alnPts;

			print "FAILURE ($MAXITER) ";

			@alnPts = @{$corpus->{$senNum}->{'Align'}->{'aln'}->[$rootNode]};
			$subTreeAligns{$rootNode}->{'alnPts'} = \@alnPts;
			$subTreeAligns{$rootNode}->{'srcNode'} = "-";

			my($leftPt) = 200;
			my($rightPt) = -1;

			foreach $child (@{$Dep->[$rootNode]->{'attch'}}) {
				if($leftPt>$subTreeAligns{$child}->{'leftPt'}) {
					$leftPt = $subTreeAligns{$child}->{'leftPt'};
				}
				if($rightPt<$subTreeAligns{$child}->{'rightPt'}) {
					$rightPt = $subTreeAligns{$child}->{'rightPt'};
				}
				$subTreeAligns{$rootNode}->{'nodesChildren'} += $subTreeAligns{$child}->{'nodesChildren'} ;
				$subTreeAligns{$rootNode}->{'tgtNodes'} += $subTreeAligns{$child}->{'tgtNodes'} ;
			}
			foreach $alnPt (@alnPts) {
				if($leftPt>$alnPt) {
					$leftPt = $alnPt;
				}	
				if($rightPt<$alnPt) {
					$rightPt = $alnPt;
				}
				$subTreeAligns{$rootNode}->{'tgtNodes'}++;
			}
			$subTreeAligns{$rootNode}->{'leftPt'} = $leftPt;
			$subTreeAligns{$rootNode}->{'rightPt'} = $rightPt;
			$subTreeAligns{$rootNode}->{'nodesChildren'} ++;

			$numFailures++;
			print " PRED $Beam->[$i]->{'srcNode'} =>".join('~',@{$Beam->[0]->{'alnPts'}})." \n";
		}
		else {
			print "SUCCESS ($iter)\n";
#			print "HURRAY !! Mistakes eliminated@@@@@@@\n";
			foreach $node (keys %{$Beam->[0]->{'srcPts'}}) {
				$subTreeAligns{$node} = $Beam->[0];
			}
			$numUpdates+=$iter;
		}

#		print "Best Alignment ($senNum)\n";
#		foreach $comp (sort {$a<=>$b} keys %subTreeAligns) {
#			if($comp==$rootNode) {
#				print "*";
#			}
#			print $comp." - $subTreeAligns{$comp} ".$subTreeAligns{$comp}->{'srcNode'}." - ".join('_',@{$subTreeAligns{$comp}->{'alnPts'}})."\n";
#		}
#		print "===============\n";
	}
	else {
		my @alnPts;

#		print "Copying (Many-Some) : $rootNode\n";
		print "COPIED \n";

		@alnPts = @{$corpus->{$senNum}->{'Align'}->{'aln'}->[$rootNode]};
		$subTreeAligns{$rootNode}->{'alnPts'} = \@alnPts;
		$subTreeAligns{$rootNode}->{'srcNode'} = "-";

		my($leftPt) = 200;
		my($rightPt) = -1;

		foreach $child (@{$Dep->[$rootNode]->{'attch'}}) {
			if($leftPt>$subTreeAligns{$child}->{'leftPt'}) {
				$leftPt = $subTreeAligns{$child}->{'leftPt'};
			}
			if($rightPt<$subTreeAligns{$child}->{'rightPt'}) {
				$rightPt = $subTreeAligns{$child}->{'rightPt'};
			}
			$subTreeAligns{$rootNode}->{'nodesChildren'} += $subTreeAligns{$child}->{'nodesChildren'} ;
			$subTreeAligns{$rootNode}->{'tgtNodes'} += $subTreeAligns{$child}->{'tgtNodes'} ;
		}
		foreach $alnPt (@alnPts) {
			if($leftPt>$alnPt) {
				$leftPt = $alnPt;
			}	
			if($rightPt<$alnPt) {
				$rightPt = $alnPt;
			}
			$subTreeAligns{$rootNode}->{'tgtNodes'} ++;
		}
		$subTreeAligns{$rootNode}->{'leftPt'} = $leftPt;
		$subTreeAligns{$rootNode}->{'rightPt'} = $rightPt;
		$subTreeAligns{$rootNode}->{'nodesChildren'} ++;

		
		$numCopied++;

	}
#	print "-----------------------------------------------------------\n";
	$totalNodes++;
}

sub decodeNode {
	
	my($corpus) = shift;
	my($senNum) = shift;
	my($rootNode) = shift;
	my($Parameters) = shift;
	my($Beam,$node);

	my($SDep) = $corpus->{$senNum}->{'SDep'};
	my($TDep) = $corpus->{$senNum}->{'TDep'};

	my($child);
	foreach $child (@{$SDep->[$rootNode]->{'attch'}}) {
		$corpus->decodeNode($senNum,$child,$Parameters);
	}

	print STDERR "DECODING NODE $rootNode\t";
	my(@srcNodes) = $corpus->getSrcNodes($senNum,$rootNode,0);
	my(@secondNodes) = $corpus->getSecondSrcNodes($senNum,\@srcNodes,$rootNode);
	push(@srcNodes,@secondNodes);
	my(@thirdNodes) = $corpus->getThirdSrcNodes($senNum,\@secondNodes,$rootNode);
	push(@srcNodes,@thirdNodes);

#	print " - - - GOLD FEATURES - - - $rootNode-\n";
#	$corpus->{$senNum}->{'nodeFeatures'}->[$rootNode]->print();
#	print " - - - - - - - - - - - - -\n";

	$Beam = &getKBestTrans($corpus,$senNum,$rootNode,\@srcNodes,$Parameters,$C{'K'});
	print STDERR "\n";

	#$corpus->{$senNum}->{'TDep'}->printTree($SDep->[$rootNode]->{'align'});
	#$corpus->{$senNum}->{'nodeFeatures'}->[$rootNode]->print();
	$Beam->[0]->{'tTree'}->printTree();
	#$Beam->[0]->{'nodeFeats'}->print();

	#print STDERR "Tree at $rootNode\n";
	$subTreeTrans{$rootNode}->{'tTree'} = $Beam->[0]->{'tTree'};
	#print "-----------------------------------------------------------\n";
	#print STDERR "\n";
	$totalNodes++;

}


sub trainNodeDecode {
	
	my($corpus) = shift;
	my($senNum) = shift;
	my($rootNode) = shift;
	my($Parameters) = shift;
	my($Beam,$node);

	my($SDep) = $corpus->{$senNum}->{'SDep'};
	my($TDep) = $corpus->{$senNum}->{'TDep'};

	my($child);
	foreach $child (@{$SDep->[$rootNode]->{'attch'}}) {
		$corpus->trainNodeDecode($senNum,$child,$Parameters);
	}

	print STDERR "TRAIN NODE $rootNode\t";
	my(@srcNodes) = $corpus->getSrcNodes($senNum,$rootNode,0);
	my(@secondNodes) = $corpus->getSecondSrcNodes($senNum,\@srcNodes,$rootNode);
	push(@srcNodes,@secondNodes);
	my(@thirdNodes) = $corpus->getThirdSrcNodes($senNum,\@secondNodes,$rootNode);
	push(@srcNodes,@thirdNodes);

#	print " - - - GOLD FEATURES - - - $rootNode-\n";
#	$corpus->{$senNum}->{'nodeFeatures'}->[$rootNode]->print();
#	print " - - - - - - - - - - - - -\n";

	$Beam = &getKBestTrans($corpus,$senNum,$rootNode,\@srcNodes,$Parameters,$C{'K'});
#	print STDERR "Best Predicted Structure : ".$Beam->[0]->{'srcNode'}."\n";
#	$Beam->[0]->{'tTree'}->printTree();	
	my($mtks) = &getTransMistakes($rootNode,$SDep,$TDep,$Beam->[0]);

#	print STDERR "Score :".$Beam->[0]->{'score'}.", ";
#	print STDERR "Mistakes: ".$mistakes."\n";


	if(! $exclude{$rootNode}) {
	
		my($iter) = 0;
		while($mtks=&getTransMistakes($rootNode,$SDep,$TDep,$Beam->[0]) && $iter<$MAXITER) {

			my $i;
			my $PredFeatArray = [];
			my $mistakeArray = [];

#			print STDERR "*****Updating Parameters ($mtks) ****************\n";
#			print STDERR " ---  GOLD --- $rootNode (of $senNum)--- ";
#			$corpus->{$senNum}->{'TDep'}->printTree();
#			$corpus->{$senNum}->{'nodeFeatures'}->[$rootNode]->print();

#			print STDERR "Score = ".$Parameters->getScore($corpus->{$senNum}->{'nodeFeatures'}->[$rootNode])."\n";
#			print STDERR " - - - PREDICTIONS - - - -\n";

			for($i=0;$i<@{$Beam};$i++) {
				$PredFeatArray->[$i] = $Beam->[$i]->{'nodeFeats'};
				$mistakeArray->[$i] = &getTransMistakes($rootNode,$SDep,$TDep,$Beam->[$i]);

#				print STDERR "Prediction $i ($Beam->[$i]->{'srcNode'})---\n";
#				print $Beam->[$i]->{'tTree'}->printTree();
#				$PredFeatArray->[$i]->print();
#				print STDERR "Score = ".$Parameters->getScore($PredFeatArray->[$i])."\n";
#				print STDERR "Mistakes = $mistakeArray->[$i]\n";
#				print STDERR "- - - - - - - -\n\n";
			}

			$newK = scalar(@{$Beam});

			$Parameters->updateParams($corpus->{$senNum}->{'nodeFeatures'}->[$rootNode],$PredFeatArray,$mistakeArray,$newK);

#			print STDERR "New Parameters :\n";
#			$Parameters->list();
#			print STDERR "--------------------\n";
			undef $Beam;
			$Beam = &getKBestTrans($corpus,$senNum,$rootNode,\@srcNodes,$Parameters,$C{'K'});

			$iter++;
		}

		if($iter==$MAXITER) {
			print STDERR "Updates FAILURE - $mtks ($MAXITER)...\n"; 
		}
		elsif($mtks==0) {
			print STDERR "Updates Successful - $mtks ($iter/$MAXITER)...\n";
		}

		$numUpdates+=$iter;
	}
	else {
		print STDERR "Not updated ...\n";
	}

#	$corpus->{$senNum}->{'TDep'}->printTree($SDep->[$rootNode]->{'align'});
#	$corpus->{$senNum}->{'nodeFeatures'}->[$rootNode]->print();
#	$Beam->[0]->{'tTree'}->printTree();
#	$Beam->[0]->{'nodeFeats'}->print();
	$subTreeTrans{$rootNode}->{'tTree'} = $Beam->[0]->{'tTree'};
#	print "-----------------------------------------------------------\n";
#	print STDERR "\n";
	$totalNodes++;
}

sub getManySomeGold {

	my($corpus) = $_[0];
	my($senNum) = $_[1];
	my($rootNode) = $_[2];
	my($item); 
	my(@openList);
	my(%onlyChildren,@childArray);

	my($GoldAlign) = $corpus->{$senNum}->{'Align'};
	my($Dep) = $corpus->{$senNum}->{'SDep'};

	my(@rootAlnPts) = @{$GoldAlign->{'aln'}->[$rootNode]};

	my($srcNode);

	if(@rootAlnPts==0) {
		my $child;
		foreach $child (@{$Dep->[$rootNode]->{'attch'}}) {
			push(@childArray,$child);
		}
		return ("l0~$rootNode",\@childArray);
	}

	$onlyChildren{$rootNode} = 1;
	push(@openList,"l0~$rootNode");

	while($item=pop(@openList)) {
		my($level,$node);
		$item=~/l([0-9]+)~([0-9]+)/;
		$node=$2;
		$level=$1;

		my (@newAlnPts) = @{$GoldAlign->{'aln'}->[$node]};
	        my (@commonPts);

#		print STDERR " Matching Root $rootNode with $node\n";
#		print STDERR " Root=".join('-',@rootAlnPts)." Node=".join('-',@newAlnPts)."\n";
		if(&matchArr(\@rootAlnPts,\@newAlnPts)) {
			$srcNode.=$item." ";
			my($child);

			foreach $child (@{$Dep->[$node]->{'attch'}}) {
				push(@openList,"l".eval($level+1)."~".$child);
				$onlyChildren{$child} = 1;
			}

			$onlyChildren{$node} = 0;
		}
#		print STDERR " SrcNode = $srcNode\n";
	}

	foreach $item (sort {$a<=>$b} keys %onlyChildren) {
		if($onlyChildren{$item}) {
			push(@childArray,$item);
		}
	}

	$srcNode=~s/\s*$//g;
	return ($srcNode,\@childArray);

}

sub getTransMistakes {

	my($rootNode) = $_[0];
	my($SDep) = $_[1];
	my($TDep) = $_[2];
	my($transInfo) = $_[3];
	
	my($trootNode) = $SDep->[$rootNode]->{'align'};
	my($srcNode) = $SDep->[$rootNode]->{'srcNode'};

	my($PTDep) = $transInfo->{'tTree'};
	my($ptrootNode) = $#$PTDep;

	my($mistakes) = 0;

	if($ptrootNode==-1) {
		return $mistakes;
	}


# srcNode not equal	
# root not equal

	if($srcNode ne $transInfo->{'srcNode'}) {
		$mistakes++;
#		print STDERR " ===== $srcNode NE $transInfo->{'srcNode'}\n";
	}

	if(($TDep->[$trootNode]->{'rt'} ne $PTDep->[$ptrootNode]->{'rt'}) || ($TDep->[$trootNode]->{'vib'} ne $PTDep->[$ptrootNode]->{'vib'})) {
		$mistakes++;
#		print STDERR "  $TDep->[$trootNode]->{'rt'}-$PTDep->[$ptrootNode]->{'rt'}-$TDep->[$trootNode]->{'vib'}-$PTDep->[$ptrootNode]->{'vib'}  ====== RootVibXX\n";
	}

	if(($TDep->[$trootNode]->{'tense'} ne $PTDep->[$ptrootNode]->{'tense'}) || ($TDep->[$trootNode]->{'gnp'} ne $PTDep->[$ptrootNode]->{'gnp'})) {
		$mistakes++;
	}


	# The mistake with reordering needs to be taken into account

	my(%relPositions,$String,$PString);

	$relPositions{$TDep->[$trootNode]->{'srcPos'}} = 0;
	foreach my $child (@{$TDep->[$trootNode]->{'attch'}}) {
		$relPositions{$TDep->[$child]->{'srcRole'}} = $TDep->[$child]->{'relPos'};
	}
	foreach my $element (sort {$relPositions{$a}<=>$relPositions{$b}} keys %relPositions) {
		$String.=$element."-";
	}
	$String=~s/-$//g;

	%relPositions=();
	$relPositions{$PTDep->[$ptrootNode]->{'srcPos'}} = 0;
	foreach my $child (@{$PTDep->[$ptrootNode]->{'attch'}}) {
		$relPositions{$PTDep->[$child]->{'srcRole'}} = $PTDep->[$child]->{'relPos'};
	}
	foreach my $element (sort {$relPositions{$a}<=>$relPositions{$b}} keys %relPositions) {
		$PString.=$element."-";
	}
	$PString=~s/-$//g;

	if($String ne $PString) {
#		print STDERR " ====== $String NE $PString\n";
		$mistakes++;
	}

	if($mistakes>0) {
		return 1;
	}
	else {
		return 0;
	}
}
sub flattenTree 
{
	$TDep = shift;
	$trootNode = shift;
	foreach my $child (@{$TDep->[$trootNode]->{'attch'}}) 
	{
		$phrase = &flattenTree($TDep,$child);
		$total.=$phrase." ";
	}

	$total = $total.$TDep->[$child]->{'rt'}."(0)";
	@array = split(/\s/,$total);

	%relPositions = ();
	foreach $element (@array)
	{
		$element =~ /(.*)\((.*)\)/;
		$posi = $1;
		$word = $2;
		$relPositions{ $word } = $posi;
	}
	
	foreach my $element (sort {$relPositions{$a}<=>$relPositions{$b}} keys %relPositions) {
		$string.=$element."_";
	}



	$posi = $TDep->[$child]->{'relPos'};
	$ret = $string."($posi)";
}

sub getMistakesNew {

	my($rootNode) = $_[0];
	my($alnInfo) = $_[1];
	my($GoldAlign) = $_[2];
	my($Dep) = $_[3];
	my(@openList) = ($rootNode);

	my(@rootAlnPts) = @{$GoldAlign->{'aln'}->[$rootNode]};

	my(%goldSrcPts);
	my(%predSrcPts) = %{$alnInfo->{'srcPts'}};


	my($item);

	# Get many-some alignment of the gold root
	$goldSrcPts{$rootNode} = 1;
	while($item=pop(@openList)) {
		my (@newAlnPts) = @{$GoldAlign->{'aln'}->[$item]};

		if(&matchArr(\@rootAlnPts,\@newAlnPts)) {
			$goldSrcPts{$item} = 1;
			my $child;
			foreach $child (@{$Dep->[$item]->{'attch'}}) {
				push(@openList,$child);
			}
		}
	}

	# Match alignments of gold and predicted
	my($extraNodes) = 0;
	foreach $item (keys %predSrcPts) {
		if(! $goldSrcPts{$item}) {
			$extraNodes++;
		}
	}
	foreach $item (keys %goldSrcPts) {
		if(! $predSrcPts{$item}) {
			$extraNodes++;
		}
	}

#	print "Comparing node ".join('~',keys %predSrcPts)." with ".join('~',keys %goldSrcPts)."\n";
			
	# Get Alignment Mistakes
	my($alignmentMistakes) = 0;
	foreach $item (@rootAlnPts) {
		my $item2;
		$exists = 0;
		foreach $item2 (@{$alnInfo->{'alnPts'}}) {
			if($item==$item2) {
				$exists=1;
				last;
			}
		}
		if($exists==0) {
			$alignmentMistakes++;
		}
	}
	foreach $item (@{$alnInfo->{'alnPts'}}) {
		my $item2;
		$exists = 0;
		foreach $item2 (@rootAlnPts) {
			if($item==$item2) {
				$exists=1;
				last;
			}
		}
		if($exists==0) {
			$alignmentMistakes++;
		}
	}
#	print "Comparing Alignments ".join('~',@{$alnInfo->{'alnPts'}})." with ".join('~',@rootAlnPts)."\n";
	
#	print "Mistakes == ".eval($extraNodes+$alignmentMistakes)."\n";
	return $extraNodes+$alignmentMistakes;
}

sub getKBestTrans {

	my($corpus) = shift;
	my($senNum) = shift;
	my($rootNode) = shift;
	my($srcNodes) = shift;
	my($Parameters) = shift;
	my($K) = shift;

	my($srcNode);
	my($transPQ) = new PQ;
	my($SDep) = $corpus->{$senNum}->{'SDep'};
	my($TDep) = $corpus->{$senNum}->{'TDep'};
	my($engsen) = $corpus->{$senNum}->{'SSen'};
	my($hinsen) = $corpus->{$senNum}->{'TSen'};

#	print STDERR "IN K-Best\n";

	my($numPoss) = 0;
	my($ltransPQ) = new PQ;

	my($candidates) = 0;
	foreach $srcNode (@$srcNodes) {

		my(@children);
		my(%nodes) = ();
		my(@components) = split(/\s+/,$srcNode);

		$srcNode=~/l0~([0-9]+)/;
		my($sword) = $1;
		my($role) = $SDep->[$sword]->{'role'};
		my($srcPos) = $engsen->[$sword]->{'pos'};
		my($tense) = $engsen->[$sword]->{'tense'};
		my($gnp) = $engsen->[$sword]->{'gnp'};

		#print STDERR "ROLE = $role\n";

		my($srcNodeWord);
		# Get Children of all Nodes that are part of $srcNode
		foreach $component (@components) {
			my($level,$node) = split(/~/,$component);
			$nodes{$node} = 1;
			push(@children,@{$SDep->[$node]->{'attch'}});
			$srcNodeWord.="$level~".$engsen->[$node]->{'root'}."~".$engsen->[$node]->{'pos'}."___";
		}	
		$srcNodeWord=~s/___$//g;

		# Push the Children of the $srcNode
		# Do not consider many-to-many entities as children
		# This is for features extraction
		my(@onlyChildren);
		my($child);
		foreach $child (@children) {
			if(! $nodes{$child}) {
				push(@onlyChildren,$child);
			}
		}

#		print STDERR "$srcNode : ";
#		foreach $child (@onlyChildren) {
#			print STDERR "$child~";
#		}
#		print STDERR "\n";

		my $childPartialTDep = new DepTree;
		my @childPointers = ();
		foreach $child (@onlyChildren) {
			$childPoint = $childPartialTDep->mergeTree($subTreeTrans{$child}->{'tTree'});	
			push(@childPointers,$childPoint);
		}

#		print STDERR "Child Points :".join('-',@childPointers)."\n";
#		$childPartialTDep->printTree();

#		print STDERR "Merged Child Tree $childPartialTDep $srcNodeWord ChildPointers = ".join('-',@childPointers)."\n";
#		print STDERR $role." is the vibh\n";

		@tRoots = Features::getEntriesTable("TreeletRootSrc",$srcNodeWord);
		@vibs = Features::getEntriesTable("Role2VibSrc",$role);
		@tenses = Features::getEntriesTable("Tense2TenseSrc",$tense);
		@gnps = Features::getEntriesTable("Gnp2GnpSrc",$gnp);



		@tRoots = ("NULL") if($#tRoots==-1);
		@vibs = ("NULL") if ($#vibs==-1);
		@tenses = ("NULL") if($#tenses==-1);
		@gnps = ("NULL") if($#gnps==-1);

		foreach $tRoot (@tRoots) {
			$t = $tRoot;
			$t=~s/_/---/g;
		foreach $vib (@vibs) {
		foreach $tense (@tenses) {
		foreach $gnp (@gnps) {

		#	print STDERR "Considering Transformation ($srcNodeWord) : $tRoot $vib $tense $gnp\n";

			my $localString="$srcPos\[$t\+$vib\+$tense\+$gnp\]";

			my $TDep = new DepTree;

			$TDep->createnode(0);
			$TDep->addroot(0);

			$TDep->addFac(0,'rt',$tRoot);
			$TDep->addFac(0,'vib',$vib);
			$TDep->addFac(0,'tense',$tense);
			$TDep->addFac(0,'gnp',$gnp);
			$TDep->addFac(0,'srcRole',$role);
			$TDep->addFac(0,'srcPos',$srcPos);
			$TDep->addFac(0,'localString',$localString);

			my($Feat) = new Features;
			$Feat->getnodeTransFeats($srcNode,0,$engsen,$SDep,$TDep,$onlyChildren,"u");
			my $score = $Parameters->getScore($Feat);
#			print STDERR "Score : $score\n\n";
		
			my($newTDep) = new DepTree;
			$newTDep->copyTree($childPartialTDep);
#			$newTDep->printDependencies();
			$newRoot = $newTDep->mergeTree($TDep);
			$newTDep->[0]->{'root'} = $newRoot;
			foreach $childPoint (@childPointers) {
				$newTDep->addattch($newRoot,$childPoint);
			}
	
			my($transInfo);
			$transInfo->{'srcNode'} = $srcNode;
			$transInfo->{'tTree'} = $newTDep;
			$transInfo->{'nodeFeats'} = $Feat;
			
			$ltransPQ->push_heap($transInfo,$score);
			$candidates++;
		}
		}
		}
		}
	}

#	if($candidates==0) {
#		my $TDep = new DepTree;
#
#		$TDep->createnode(0);
#		$TDep->addroot(0);
#
#		$TDep->addFac(0,'rt',"NULL");
#		$TDep->addFac(0,'vib',"NULL");
#		$TDep->addFac(0,'tense',"NULL");
#		$TDep->addFac(0,'gnp',"NULL");
#		$TDep->addFac(0,'srcRole',"");
#		$TDep->addFac(0,'srcPos',"NULL");
#		$TDep->addFac(0,'localString',"");
#
#		my($Feat) = new Features;
#
#		my($newTDep) = new DepTree;
#		$newTDep->copyTree($childPartialTDep);
##		$newTDep->printDependencies();
#		$newRoot = $newTDep->mergeTree($TDep);
#		$newTDep->[0]->{'root'} = $newRoot;
#		foreach $childPoint (@childPointers) {
#			$newTDep->addattch($newRoot,$childPoint);
#		}
#	
#
#		my($transInfo);
#		$transInfo->{'srcNode'} = "";
#		$transInfo->{'tTree'} = $newTDep;
#		$transInfo->{'nodeFeats'} = $Feat;
#			
#		$ltransPQ->push_heap($transInfo,$score);
#		
#	}
	print STDERR "a";

	# Get permutations for 0...$#attch, $#attch+1
	# Compute relative positions and then features

	my $transPQ = new PQ;

	my(@transinfs) = ();
	my($maxScore);
	for($i=0;$i<$K && !$ltransPQ->empty();$i++) {
		my($transInfo,$score) = $ltransPQ->pop_heap();

		my($srcNode) = $transInfo->{'srcNode'};
		my($rootIndex) = $transInfo->{'tTree'}->[0]->{'root'};
		my($string) = "$rootIndex&";
		my(@onlyChildren);

		my $localString = $transInfo->{'tTree'}->[$rootIndex]->{'localString'};

		foreach $child (@{$transInfo->{'tTree'}->[$ootIndex]->{'attch'}}) {
			$string.=" $child";	
			push(@onlyChildren,$child);
		}

		if(@onlyChildren!=0) {
			if(@onlyChildren<=4) {
				@permStrings = &permuteString($string);
			}
			else {
				@permStrings = &relposString($string);
			}

			foreach $relposComb (@permStrings) {
				my(@tgtChildren) = split(/_/,$relposComb);
				my($newTDepTree) = new DepTree;
				$newTDepTree->copyTree($transInfo->{'tTree'});

				$subTreeString="";
				$headsString="";

				my($foundRoot)=0;
				foreach my $tgtChInfo (@tgtChildren) {
					($tgtChild,$relativePos) = split(/,/,$tgtChInfo);
					$newTDepTree->addFac($tgtChild,"relPos",$relativePos);
					#print STDERR "relPos of $tgtChild = $relativePos\n";

					if($foundRoot==0 && $relativePos>0) {
						$subTreeString.=$localString."___" if($localString);
						$headsString.=$localString."&___" if($localString);
						$foundRoot=1;
					}

					my($s);
					$s=$newTDepTree->[$tgtChild]->{'subTreeString'};
					$s=~s/\]\&/\]/g;
					$subTreeString.=$s."___" if($s);
					$s=$newTDepTree->[$tgtChild]->{'localString'};
					$headsString.=$s."___" if($s);

					#print STDERR " +++".$subTreeString."\n";
				}
				if($foundRoot==0) {
					$subTreeString.=$localString."___" if($localString);
					$headsString.=$localString."&___" if($localString);
				}
				$subTreeString=~s/___$//g;
				$headsString=~s/___$//g;
				#print STDERR "$subTreeString\t".join('xxx',@tgtChildren)."\n";

				$newTDepTree->addFac($rootIndex,'subTreeString',$subTreeString);
				$newTDepTree->addFac($rootIndex,'headsString',$headsString);

				my($Feat) = new Features;
				$Feat->getnodeTransFeats($srcNode,$rootIndex,$engsen,$SDep,$newTDepTree,\@onlyChildren,"u");
				my $score = $Parameters->getScore($Feat);

#				print STDERR "Order Thing : srcNode=$srcNode, RootIndex=$rootIndex\n";
#				$newTDepTree->printTree();
#				$Feat->print();
#				print STDERR "Score = $score\n";

				my($newTransInfo);
				$newTransInfo->{'srcNode'} = $srcNode;
				$newTransInfo->{'tTree'} = $newTDepTree;
				$newTransInfo->{'nodeFeats'} = $Feat;

				$transPQ->push_heap($newTransInfo,$score);
			}
		}
		else {
			my($newTransInfo);
			$newTransInfo->{'srcNode'} = $transInfo->{'srcNode'};
			$newTransInfo->{'tTree'} = $transInfo->{'tTree'};

			$newTransInfo->{'tTree'}->addFac($rootIndex,'subTreeString',$localString);
			$newTransInfo->{'tTree'}->addFac($rootIndex,'headsString',$localString);

			my($Feat) = new Features;
			$Feat->getnodeTransFeats($srcNode,$rootIndex,$engsen,$SDep,$newTransInfo->{'tTree'},\@onlyChildren,"u");
			my $score = $Parameters->getScore($Feat);

			$newTransInfo->{'nodeFeats'} = $Feat;

			$transPQ->push_heap($newTransInfo,$score);
		}
	}
	print STDERR "b";

	for($i=0;$i<$K && !$transPQ->empty();$i++) {
		my($transInfo,$score) = $transPQ->pop_heap();
		$transinfs[$i]->{'srcNode'} = $transInfo->{'srcNode'};
		$transinfs[$i]->{'tTree'} = $transInfo->{'tTree'};
		$transinfs[$i]->{'nodeFeats'} = $transInfo->{'nodeFeats'};

		$transinfs[$i]->{'score'} = $score;
	}
	print STDERR "c";

	return \@transinfs;
}

sub permuteString {

	my($string) = shift;
	my @toPermute = split(/\s/,$string);
	my $perm = new List::Permutor @toPermute;
	my @permutedStrings;

	while (my @set = $perm->next) {
		$num = @set;
		$rootPos = -1;
		for($k = 0; $k < $num; $k++) {
			if($set[$k] =~ /&$/) {
				$rootPos = $k;
				last;
			}
		}
		for($k = 0; $k < $num; $k++) {
			$pos = $k - $rootPos;
			$set[$k] .= ",$pos";
		}
		splice(@set,$rootPos,1);
		push(@permutedStrings,join('_',@set));
	}
	return @permutedStrings;
}

sub relposString {
	my($string) = shift;
	my(@set) = split(/\s+/,$string);
	my $num = @set;
	my  @permutedStrings;

	my $rootPos = -1;
	for(my $k = 0; $k < $num; $k++) {
		if($set[$k] =~ /&$/) {
			$rootPos = $k;
			last;
		}
	}
	my $pos;
	for(my $k = 0; $k < $num; $k++) {
		$pos = $k - $rootPos;
		$set[$k] .= ",$pos";
	}
	splice(@set,$rootPos,1);
	push(@permutedStrings,join('_',@set));

	return @permutedStrings;
}

sub getKBestAligns {

	my($corpus) = shift;
	my($senNum) = shift;
	my($rootNode) = shift;
	my($srcNodes) = shift;
	my($Parameters) = shift;
	my($K) = shift;

	my($srcNode);
	my($alignPQ) = new PQ;
	my($Dep) = $corpus->{$senNum}->{'SDep'};
	my($engsen) = $corpus->{$senNum}->{'SSen'};
	my($hinsen) = $corpus->{$senNum}->{'TSen'};
	my($GoldAlign) = $corpus->{$senNum}->{'Align'};

	my($numPoss) = 0;

#	print "Source words Aligned till now :";
#	foreach $comp (keys %subTreeAligns) {
#		print "$comp ";
#	}
#	print "\n";

	foreach $srcNode (@$srcNodes) {
		my(@children);
		my(%nodes) = ();
		my(@components) = split(/\s+/,$srcNode);

		# Get Children of all Nodes that are part of $srcNode
		foreach $component (@components) {
			my($level,$node) = split(/~/,$component);
			$nodes{$node} = 1;
			push(@children,@{$Dep->[$node]->{'attch'}});
		}	

		# Push the Children of the $srcNode
		# Do not consider many-to-many entities as children
		# This is for features extraction
		my(@onlyChildren);
		my($child);
		foreach $child (@children) {
			if(! $nodes{$child}) {
				push(@onlyChildren,$child);
			}
		}

#		print "$srcNode : ";
#		foreach $child (@onlyChildren) {
#			print "$child~";
#		}
#		print "\n";

		my $AlignChildren = new Align;
#		print "PrevAln :";
		if($C{'restricted'}==1) {
			foreach $comp (keys %subTreeAligns) {
				if(! $nodes{$comp}) {
#					print "$comp(".join(',',@{$subTreeAligns{$comp}->{'alnPts'}}).") ";	
#					$doneAlignments->mergealign($engsen,$subTreeAligns{$comp});
#					$AlignChildren->mergealign($engsen,$subTreeAligns{$comp});
					foreach $alnPt (@{$subTreeAligns{$comp}->{'alnPts'}}) {
						$AlignChildren->addalign($comp,$alnPt);
					}
				}
			}
#			print "\n";
#			print "-------------\n";
		}
		else {
			foreach $child (@onlyChildren) {
				foreach $alnPt (@{$subTreeAligns{$child}->{'alnPts'}}) {
					$AlignChildren->addalign($comp,$alnPt);
				}
			}
		}

		# Get the spans from children
		my ($leftPos) = 200;
		my ($rightPos) = -1;
		my ($nodesChildren) = 0;
		my ($tgtNodes) = 0;
		foreach $child (@onlyChildren) {
			if($leftPos>$subTreeAligns{$child}->{'leftPt'}) {
				$leftPos = $subTreeAligns{$child}->{'leftPt'};
			}
			if($rightPos<$subTreeAligns{$child}->{'rightPt'}) {
				$rightPos = $subTreeAligns{$child}->{'rightPt'};
			}
			$nodesChildren += $subTreeAligns{$child}->{'nodesChildren'};
			$tgtNodes += $subTreeAligns{$child}->{'tgtNodes'};
		}

		my(@tgtPossibilities) = &getTgtPossibilities($engsen,$AlignChildren,$hinsen);

		my($possibility);

		foreach $possibility (@tgtPossibilities) {
			my $Feat = new Features;
			my $newAlign = new Align;
			my ($newLeftPos) = $leftPos;
			my ($newRightPos) = $rightPos;
			my ($newNodesChildren) = $nodesChildren;
			my ($newTgtNodes) = $tgtNodes;

			my @alnPts;
			$newAlign->copy2($AlignChildren);

#			print "Possibility = $possibility\n";
#			print "SrcNode = '$srcNode'\n";

			#All the alignments of the possibility
			@alnPts = split(/-/,$possibility);
			foreach $alnPt (@alnPts) {
				while($srcNode=~/\~([0-9]+)/g) {
					my($srcWord) = $1;
					$newAlign->addalign($srcWord,$alnPt);
				}
				if($alnPt<$newLeftPos) {
					$newLeftPos = $alnPt;
				}
				if($alnPt>$newRightPos) {
					$newRightPos = $alnPt;
				}
			}
			$newTgtNodes += scalar(@alnPts);
			$newNodesChildren += scalar(@components);

#			$newAlign->print($engsen);

			$srcNode=~/l0~([0-9]+)/;
			$Feat->getnodeFeaturesNew($srcNode,$engsen,$hinsen,$Dep,$newAlign,"p",\@onlyChildren);
#			$Feat->addSpanNodeFeats($newLeftPos,$newRightPos,$newNodesChildren,$newTgtNodes);
#			$Feat->print();
#			print "Features $Feat:\n";
#			foreach $feat (keys %$Feat) {
#				print "$feat--".$Feat->{$feat}."\n";
#			}

			my $score = $Parameters->getScore($Feat);
			$newAlign->{'score'} = $score;
#			print "Score = $score\n";

			my($alnInfo) = {};
			$alnInfo->{'alnPts'} = \@alnPts;
			$alnInfo->{'srcNode'} = $srcNode;
			$alnInfo->{'srcPts'} = \%nodes;
			$alnInfo->{'nodeFeats'} = $Feat;
			$alnInfo->{'leftPt'} = $newLeftPos;
			$alnInfo->{'rightPt'} = $newRightPos;
			$alnInfo->{'nodesChildren'} = $newNodesChildren;
			$alnInfo->{'tgtNodes'} = $newTgtNodes;
			$alignPQ->push_heap($alnInfo,$score);
			#$alignPQ->push_heap($newAlign,$score);

			$numPoss++;
		}
	}

	my(@alninfs) = ();
	my($maxScore);
	for($i=0;$i<$K && !$alignPQ->empty();$i++) {
		my($alnInfo,$score) = $alignPQ->pop_heap();
		$alninfs[$i]->{'alnPts'} = $alnInfo->{'alnPts'};
		$alninfs[$i]->{'srcNode'} = $alnInfo->{'srcNode'};
		$alninfs[$i]->{'srcPts'} = $alnInfo->{'srcPts'};
		$alninfs[$i]->{'nodeFeats'} = $alnInfo->{'nodeFeats'};
		$alninfs[$i]->{'leftPt'} = $alnInfo->{'leftPt'};
		$alninfs[$i]->{'rightPt'} = $alnInfo->{'rightPt'};
		$alninfs[$i]->{'nodesChildren'} = $alnInfo->{'nodesChildren'};
		$alninfs[$i]->{'tgtNodes'} = $alnInfo->{'tgtNodes'};
	}

#	$alignBeam->[0]->print($engsen);
#	print "------------------\n";


#	print "Best Alignment\n";
#	foreach $comp (sort {$a<=>$b} keys %subTreeAligns) {
#		print $comp." - $subTreeAligns{$comp} ".$subTreeAligns{$comp}->{'srcNode'}." - ".join('_',@{$subTreeAligns{$comp}->{'alnPts'}})."\n";
#	}
#	print "===============\n";

	return \@alninfs;

}

sub getKBestAlignsKBestChildren {

	my($corpus) = shift;
	my($senNum) = shift;
	my($rootNode) = shift;
	my($srcNodes) = shift;
	my($Parameters) = shift;
	my($K) = shift;

	my($srcNode);
	my($alignPQ) = new PQ;
	my($Dep) = $corpus->{$senNum}->{'SDep'};
	my($engsen) = $corpus->{$senNum}->{'SSen'};
	my($hinsen) = $corpus->{$senNum}->{'TSen'};
	my($GoldAlign) = $corpus->{$senNum}->{'Align'};
	my($Beam) = [];

	my($numPoss) = 0;

	foreach $srcNode (@$srcNodes) {
		my(@children);
		my(%nodes) = ();
		my(@components) = split(/\s+/,$srcNode);

		# Get Children of all Nodes that are part of $srcNode
		foreach $component (@components) {
			my($level,$node) = split(/~/,$component);
			$nodes{$node} = 1;
			push(@children,@{$Dep->[$node]->{'attch'}});
		}	

		# Push the Children of the $srcNode
		# Do not consider many-to-many entities as children
		# This is for features extraction
		my(@onlyChildren);
		my($child);
		foreach $child (@children) {
			if(! $nodes{$child}) {
				push(@onlyChildren,$child);
			}
		}

#		print "Children of $srcNode = ".join(',',@onlyChildren)."\n";
#		print "Number of Nodes ".scalar(keys %nodes)."\n";

		my($globalPQ) = new PQ;
		my($oneAlign);
		my($onePriority);
		my(%insertedAligns,$insertedKey) = ();

		$onePriority = 0;
		foreach $i (@onlyChildren)  #only the node and there children.
		{
			$oneAlign->{$i} = 0;
			$onePriority += $subTreeAligns{$i}->[0]->{'score'};		

			$insertedKey.="0_";
		}

		$globalPQ->push_heap($oneAlign,$onePriority);
		$insertedKey=~s/_$//g;
		$insertedAligns{"$insertedKey"} = 1;


		my($GenAlign);

#		print "$srcNode : ";
		for($k=0;$k<$C{'K'};$k++) {

			if($globalPQ->empty()) {
				$newK = $k;
				last;
			}

			($oneAlign,$onePriority) = $globalPQ->pop_heap();

			#print "\n$onePriority: ".join(' ',%{$oneAlign})."\n";
			$Beam->[$k] = new Align;
			$GenAlign = $Beam->[$k];
			#print "$k $GenAlign\n";

			foreach $i (@onlyChildren) {
				$GenAlign->mergealign($engsen,$subTreeAligns{$i}->[$oneAlign->{$i}]->{'align'});
			}
			$GenAlign->{'score'} = $onePriority;


			# Put in the Global Beam
			foreach $i (@onlyChildren) {

				my(%newArr) = %{$oneAlign};
				my($newPriority);

				$newArr{$i} = $newArr{$i}+1;

				my($key);
				foreach $key (sort {$a<=>$b} keys %newArr) {
					$insertedKey = $newArr{$i}."_";    #?????????????????
				}
				$insertedKey =~s/_$//g;

				if(! $insertedAligns{"$insertedKey"}) {

					$newPriority = $onePriority + $subTreeAligns{$nodeId}->[$newArr{$nodeId}]->{'score'} - $subTreeAligns{$nodeId}->[$newArr{$nodeId}-1]->{'score'};
					$globalPQ->push_heap(\%newArr,$newPriority);
					$insertedAligns{"$insertedKey"} = 1;
				}
			}
		}

		if($newK==0) {
			$Beam->[0] = new Align;
			$newK = 1;
			print "No Children Exists newK = $newK\n";
		}

		for($k=0;$k<$newK;$k++) {

			my $AlignChildren = $Beam->[$k];
			my $score = $AlignChildren->{'score'};

			my(@tgtPossibilities) = &getTgtPossibilities($engsen,$AlignChildren,$hinsen);

			my($possibility);

#			print "Target Possibilities = ".join('~',@tgtPossibilities)."\n";

			foreach $possibility (@tgtPossibilities) {
				my $Feat = new Features;
				my $newAlign = new Align;

				my @alnPts;
				$newAlign->copy2($AlignChildren);

	#			print "Possibility = $possibility\n";
	#			print "SrcNode = '$srcNode'\n";

				#All the alignments of the possibility
				@alnPts = split(/-/,$possibility);
				while($srcNode=~/([xl])([0-9]+)\~([0-9]+)/g) {
					my($srcWord) = $3;
					my($srcWordType) = $1;
					$newAlign->delalign($srcWord);

					foreach $alnPt (@alnPts) {

						if($srcWordType eq "l") {
							$newAlign->addalign($srcWord,$alnPt);
						}
					}
				}

				$Feat->getnodeFeaturesNew($srcNode,$engsen,$hinsen,$Dep,$newAlign,"p",\@onlyChildren);
#				$Feat->addSpanNodeFeats($newLeftPos,$newRightPos,$newNodesChildren,$newTgtNodes);
#				$Feat->print();
#				print "Features $Feat:\n";
#				foreach $feat (keys %$Feat) {
#					print "$feat--".$Feat->{$feat}."\n";
#				}

				$newAlign->{'score'} = $score + scalar(keys %nodes) * $Parameters->getScore($Feat);
#				print "Score = $score\n";

				my($alnInfo) = {};
				$alnInfo->{'align'} = $newAlign;
				$alnInfo->{'srcNode'} = $srcNode;
				$alnInfo->{'srcPts'} = \%nodes;
				$alnInfo->{'nodeFeats'} = $Feat;
				$alnInfo->{'score'} = $newAlign->{'score'};
				$alnInfo->{'localScore'} = scalar(keys %nodes) * $Parameters->getScore($Feat);

				$alignPQ->push_heap($alnInfo,$newAlign->{'score'});
				#$alignPQ->push_heap($newAlign,$score);

				$numPoss++;
			}
		}
	}

	my(@alninfs) = ();
	my($maxScore);
#	for($i=0;$i<$C{'K'} && !$alignPQ->empty();$i++) {
	for($i=0;!$alignPQ->empty();$i++) {
		my($alnInfo,$score) = $alignPQ->pop_heap();
		$alninfs[$i]->{'align'} = $alnInfo->{'align'};
		$alninfs[$i]->{'srcNode'} = $alnInfo->{'srcNode'};
		$alninfs[$i]->{'srcPts'} = $alnInfo->{'srcPts'};
		$alninfs[$i]->{'nodeFeats'} = $alnInfo->{'nodeFeats'};
		$alninfs[$i]->{'score'} = $alnInfo->{'score'};
		$alninfs[$i]->{'localScore'} = $alnInfo->{'localScore'};
	}

	return \@alninfs;

}

sub getTgtPossibilities {
	my($engsen) = shift;
	my($Align) = shift;
	my($i,$alnPt);
	my(%Alignments);
	my($tgtsen) = shift;

	for($i=0;$i<=$#$engsen;$i++) {
		foreach $alnPt (@{$Align->{'aln'}->[$i]}) {
			$Alignments{$alnPt} = 1;
		}
	}

	my(@toAlignSet) = ();
	my(@possibilities) = ();
	my($j);

	for($i=0;$i<=$#$tgtsen;$i++) {
		if($Alignments{$i}) {
			my @newpossibilities = &AlignSetPoss(\@toAlignSet);
			@toAlignSet=();
			push(@possibilities,@newpossibilities);
		}
		else {
			push(@toAlignSet,$i);
		}
	}
	my @newpossibilities = &AlignSetPoss(\@toAlignSet);
	@toAlignSet=();
	push(@possibilities,@newpossibilities);
	push(@possibilities,"");

	return @possibilities;
	
}

sub AlignSetPoss {
	my($toAlignSetRef) = $_[0];
	my(@toAlignSet) = @$toAlignSetRef;
	my(@possibilities) = ();
	for($j=0;$j<@toAlignSet;$j++) {
		push(@possibilities,$toAlignSet[$j]);
		if(defined $toAlignSet[$j+1]) {
			push(@possibilities,"$toAlignSet[$j]-$toAlignSet[$j+1]");
		}
		if(defined $toAlignSet[$j+2]) {
			push(@possibilities,"$toAlignSet[$j]-$toAlignSet[$j+1]-$toAlignSet[$j+2]");	
			push(@possibilities,"$toAlignSet[$j]-$toAlignSet[$j+2]");	
		}
		if(defined $toAlignSet[$j+3]) {
			push(@possibilities,"$toAlignSet[$j]-$toAlignSet[$j+1]-$toAlignSet[$j+2]-$toAlignSet[$j+3]");	
			push(@possibilities,"$toAlignSet[$j]-$toAlignSet[$j+1]-$toAlignSet[$j+3]");	
			push(@possibilities,"$toAlignSet[$j]-$toAlignSet[$j+2]-$toAlignSet[$j+3]");	
			push(@possibilities,"$toAlignSet[$j]-$toAlignSet[$j+3]");	
		}
		if(defined $toAlignSet[$j+4]) {
			push(@possibilities,"$toAlignSet[$j]-$toAlignSet[$j+1]-$toAlignSet[$j+2]-$toAlignSet[$j+3]-$toAlignSet[$j+4]");	
		}
	}
	
	return @possibilities;
}

sub goldRelated {
	my($corpus) = shift;
	my($senNum) = shift;
	my($child) = shift;
	my($root) = shift;

	my(@childAlns) = @{$corpus->{'Align'}->{'aln'}->[$child]};
	my(@rootAlns) = @{$corpus->{'Align'}->{'aln'}->[$root]};

	if(&isOverlapMatch(\@childAlns,\@rootAlns)) {
		return 1;
	}
}

sub isOverlapMatch {
	my($array1) = $_[0];
	my($array2) = $_[1];

	my($ele1,$ele2);
	
	foreach $ele1 (@$array1) {
		foreach $ele2 (@$array2) {
			if($ele1==$ele2) {
				return 1;
			}
		}
	}
	return 0;
}

sub getSecondSrcNodes {
	my($corpus) = shift;
	my($senNum) = shift;
	my($srcNodes) = shift;
	my($rootNode) = shift;

	my($rootNodeWord) = $corpus->{$senNum}->{'SSen'}->[$rootNode]->{'root'};

	my($srcNode);
	my %secondSrcNodes = ();

	my($Dep) = $corpus->{$senNum}->{'SDep'};

	foreach $srcNode (@$srcNodes) {
		if($srcNode=~/^(.+)l1~([0-9]+)(.*)$/) {
			my($header) = $1; $footer = $3;
			my($nodePos) = $2;
			foreach	$child (@{$Dep->[$rootNode]->{'attch'}}) {
				if($child>$nodePos) {
					$secondSrcNodes{$header."l1~".$nodePos.$footer." l1~".$child} = 1;
				}
				elsif($child<$nodePos) {
					$secondSrcNodes{$header."l1~".$child." l1~".$nodePos.$footer} = 1;
				}
			}
		}
	}
	return keys %secondSrcNodes;
}

sub getThirdSrcNodes {
	my($corpus) = shift;
	my($senNum) = shift;
	my($srcNodes) = shift;
	my($rootNode) = shift;

	my($rootNodeWord) = $corpus->{$senNum}->{'SSen'}->[$rootNode]->{'root'};

	my($srcNode) ;
	my %thirdSrcNodes = ();

	my($Dep) = $corpus->{$senNum}->{'SDep'};

	foreach $srcNode (@$srcNodes) {
		if($srcNode=~/^(.+)l1~([0-9]+) l1~([0-9]+)$/) {
			my($header) = $1;
			my($nodePos1) = $2; $nodePos2 = $3;
			foreach	$child (@{$Dep->[$rootNode]->{'attch'}}) {

				if($child<$nodePos1) {
					$thirdSrcNodes{$header."l1~".$child." l1~".$nodePos1." l1~".$nodePos2} = 1;
				}
				elsif($child>$nodePos1 && $child<$nodePos2) {
					$thirdSrcNodes{$header."l1~".$nodePos1." l1~".$child." l1~".$nodePos2} = 1;
				}
				elsif($child>$nodePos2) {
					$thirdSrcNodes{$header."l1~".$nodePos1." l1~".$nodePos2." l1~".$child} = 1;
				}
			}
		}
	}

	return keys %thirdSrcNodes;
}

sub getSrcNodes {

	my($corpus) = shift;
	my($senNum) = shift;
	my($rootNode) = shift;
	my($height) = shift;

	my($rootNodeWord) = $corpus->{$senNum}->{'SSen'}->[$rootNode]->{'root'};

	my(@srcNodes) = ();
	push(@srcNodes,"l$height~$rootNode");

	if($height==2) {
		return @srcNodes;
	}


	my($Dep) = $corpus->{$senNum}->{'SDep'};
	my($child);
	foreach	$child (@{$Dep->[$rootNode]->{'attch'}}) {
		my @childNodes = $corpus->getSrcNodes($senNum,$child,$height+1);
		foreach $childNode (@childNodes) {
			if($height!=0) {
				push(@srcNodes,"x$height~$rootNode $childNode");	
			}
			push(@srcNodes,"l$height~$rootNode $childNode");
		}
	}

	return @srcNodes;


}


sub decode2 {

	my($corpus) = shift;
	my($senNum) = shift;
	my($Parameters) = shift;
	my($dictionary) = shift;
	my($i);

	my($Varg,$Dep);
	my($engsen,$hinsen);
	my($GoldAlign,$GenAlign,$GenAlign2);
	my($Beam,$TempBeam);
	my($LFeatures,$score);
	my($localbeam,%localbeams);
	my($k,$m,$n,$p,$i);
	my($minScore,$minPosition);
	my($hinwordpos);
	my($verbnum,$argnum);
	my($LFeatures,$GenFeatures);
	my($nengwords,$nhinwords);

	
	$Dep = $corpus->{$senNum}->{'SDep'};
	$engsen = $corpus->{$senNum}->{'SSen'};
	$nengwords = @{$engsen};

	#$hinsen = $corpus->{$senNum}->{'TSen'};
	#$nhinwords = @{$hinsen};
	#$GoldAlign = $corpus->{$senNum}->{'Align'};


	#$corpus->{$senNum}->{'StringBeam'} = new AlignBeam($C{'K'});
	#	$Beam = $corpus->{$senNum}->{'StringBeam'};

	my($s);

#	print STDERR "$senNum) words($nengwords):".scalar($nhinwords);
#	print STDERR "words($nengwords):".scalar($nhinwords)."\n\n";
	$starttime = time();

	my($obj,$priorIty);

#	$GoldAlign->printAln($engsen,$hinsen);
	#print "Decoding Node $senNum $Dep->[0]->{'root'}\n";
	my($finalbeam);

	$finalbeam = $corpus->decodenode($senNum,$Dep->[0]->{'root'},$Parameters,$dictionary);
	my($mytrans) = $finalbeam->[0]->[1];
	$mytrans=~s/_/ /g;

	print "$mytrans\n";

}


sub predictAndupdatenode
{
	my($corpus) = shift;
	my($senNum) = shift;
	my($nodeId) = shift;
	my($Parameters) = shift;
	my($ifUpdate) = shift;

	my($Varg,$Dep);
	my($engsen,$hinsen);
	my($GoldAlign,$GenAlign,$GenAlign2);
	my($Beam,$TempBeam);
	my($LFeatures,$score);
	my($localbeam,%localbeams);
	my($k,$m,$n,$p,$i);
	my($minScore,$minPosition);
	my($hinwordpos);
	my($verbnum,$argnum);
	my($GenFeatures);
	my($nengwords,$nhinwords);

	$Dep = $corpus->{$senNum}->{'SDep'};
	$engsen = $corpus->{$senNum}->{'SSen'};
	$nengwords = @{$engsen};
	$hinsen = $corpus->{$senNum}->{'TSen'};
	$nhinwords = @{$hinsen};
	$GoldAlign = $corpus->{$senNum}->{'Align'};

	$corpus->{$senNum}->{'AlignBeam'} = new AlignBeam($C{'K'});
	$Beam = $corpus->{$senNum}->{'AlignBeam'};

	my($s);

	#print STDERR "$senNum) words($nengwords):".scalar($nhinwords);
	#print "words($nengwords):".scalar($nhinwords)."\n";
	$starttime = time();

	my($obj,$priorIty);


	#Getting the Local beam of nodeId
	$localpq = new PQ;

	for($k=0;$k<=$nhinwords;$k++) # here K == nhinwords for src going to NULL
	{

		my @candwords;
		if($k!=$nhinwords)
		{ push(@candwords,$k); }

		my($LFeatures) = new Features;
		$LFeatures->getnodeLFeatures($nodeId,$engsen,$hinsen,\@candwords,"p");

		$score = $Parameters->getScore($LFeatures);

		#print "Alignment between $nodeId -> ".join('_',@candwords)." score=$score\n";
		#$LFeatures->print();

		$localpq->push_heap(\@candwords,$score);
	}

	for($k=0;$k<$nhinwords-1;$k++) {

		my @candwords;
		push(@candwords,$k); 
		push(@candwords,$k+1);

		my($LFeatures) = new Features;
		$LFeatures->getnodeLFeatures($nodeId,$engsen,$hinsen,\@candwords,"p");

		$score = $Parameters->getScore($LFeatures);

		#print "Alignment between $nodeId -> ".join('_',@candwords)." score = $score\n";
		#$LFeatures->print();

		$localpq->push_heap(\@candwords,$score);
	}

	$localbeam = new LocalBeam($nhinwords);	
	$k=0;
	while(! $localpq->empty()) {
		($obj,$priority) = $localpq->pop_heap();

		$localbeam->[$k]->[0] = $priority;
		$localbeam->[$k]->[1] = $obj;
		$k++;
	}

	$localbeams{$nodeId} = $localbeam;

	foreach $child (@{$Dep->[$nodeId]->{'attch'}})
	{
		$localbeams{$child} = $corpus->predictAndupdatenode($senNum,$child,$Parameters,$ifUpdate);
		#print "CHILD = $child $localbeams{$child}...\n";
	}
		
	my($globalPQ) = new PQ;

	my($oneAlign);
	my($onePriority);

	my(%insertedAligns,$insertedKey) = ();

	$onePriority = 0;
	foreach $i (keys %localbeams)  #only the node and there children.
	{
		$oneAlign->{$i} = 0;
		$onePriority += $localbeams{$i}->[0]->[0];		
	}

	$globalPQ->push_heap($oneAlign,$onePriority);
	$insertedKey = join('_',keys %{$oneAlign});
	$insertedAligns{"$insertedKey"} = 1;

	$time = time();
	$duration = $time - $starttime;
	$starttime = $time;
	#print STDERR " init:$duration";

	my($newK);
	$newK = $C{'K'};

	for($k=0;$k<$C{'K'};$k++) 
	{

		my($oneAlign);
		if($globalPQ->empty()) {
			$newK = $k;
			last;
		}

		($oneAlign,$onePriority) = $globalPQ->pop_heap();

		#print "\n$onePriority: ".join(' ',%{$oneAlign})."\n";

		$GenAlign = $Beam->[$k];
		#print "$k $GenAlign\n";

		foreach $i (keys %localbeams) 
		{
			my($hn);
			if($i == $nodeId) 
			{
				foreach $hn (@{$localbeams{$i}->[$oneAlign->{$i}]->[1]}) #?????
				{
					$GenAlign->addalign($i,$hn);
				}
			}
			else 
			{
				#$localbeams{$i}->[$oneAlign->{$i}]->[1]->print($engsen);
				$GenAlign->mergealign($engsen,$localbeams{$i}->[$oneAlign->{$i}]->[1]);
			}
			#$GenAlign->print($engsen);
		}
		$GenAlign->{'score'} = $onePriority;
		


		
		
		# Put in the Global Beam

		foreach $i (keys %localbeams) {

			my(%newArr) = %{$oneAlign};
			my($newPriority);

			$newArr{$i} = $newArr{$i}+1;

			my($key);
			foreach $key (sort {$a<=>$b} keys %newArr) {
				$insertedKey = $newArr{$i}."_";    #?????????????????
			}
			$insertedKey =~s/_$//g;

			if(! $insertedAligns{"$insertedKey"}) {

				$newPriority = $onePriority + $localbeams{$nodeId}->[$newArr{$nodeId}]->[0] - $localbeams{$nodeId}->[$newArr{$nodeId}-1]->[0];
				$globalPQ->push_heap(\%newArr,$newPriority);
				$insertedAligns{"$insertedKey"} = 1;
			}
		}
	}



	my($reorderPQ) = new PQ;

	$corpus->{$senNum}->{'AlignBeam'} = $Beam;

	# Recalculate the scores
	#print "Final Scores\n";
	$GenAlign = new Align($nengwords);
	#print "Alignments in the Global Beams\n";
#	print "Predict Features of $nodeId\n";


#	for($i=0;$i<$newK;$i++)
#	{
#		my($Features) = new Features;

#		$Features->getnodeFeatures($nodeId,$engsen,$hinsen,$Dep,$Beam->[$i],"p");

#		$Features->print();
		

#		$corpus->{$senNum}->{$type}->[$nodeId] = $Features;
#		$Beam->[$i]->{'score'} = $Parameters->getScore($Features);

#		$reorderPQ->push_heap($Beam->[$i],$Beam->[$i]->{'score'});
#	}

	
#	print "Gold-----------------------------\n";
#	my $gold_features;
#	$gold_features = $corpus->{$senNum}->{'nodeFeatures'}->[$nodeId];
#	$gold_features->print();

	#-------------------------------Update Parameters:
	my($obj,$priority);
	my($localbeam);

	$localbeam = new LocalBeam($newK);

	my $PredFeatArray;
	my $mistakesArray;

	$i=0;

	print "================ K-Best for Node $nodeId ===========================\n";
	#$corpus->{$senNum}->{'SFeatures'}->print();
#	$corpus->{$senNum}->{'Align'}->print($engsen);
	#print "Predictions..\n";
#	print "$senNum , Gold Features of $nodeId\n";
#	$corpus->{$senNum}->{'nodeFeatures'}->[$nodeId]->print();
	
	print "++++ Predicted Features : \n+++++";
	if($ifUpdate) {
		for($i=0;$i<$newK;$i++) {

			my($Features) = new Features;
			$Features->getnodeFeatures($nodeId,$engsen,$hinsen,$Dep,$Beam->[$i],"u");

			$PredFeatArray->[$i] = $Features;
			$mistakeArray->[$i] = $GoldAlign->getnodeMistakes($nodeId,$Beam->[$i]);
		}

		$Parameters->updateParams($corpus->{$senNum}->{'nodeFeatures'}->[$nodeId],$PredFeatArray,$mistakeArray,$newK);
	}


	for($i=0;$i<$newK;$i++)
	{
		my($Features) = new Features;

		$Features->getnodeFeatures($nodeId,$engsen,$hinsen,$Dep,$Beam->[$i],"p");

#		$Features->print();
		

#		$corpus->{$senNum}->{$type}->[$nodeId] = $Features;
		$Beam->[$i]->{'score'} = $Beam->[$i]->{'score'}+$Parameters->getScore($Features);

		$reorderPQ->push_heap($Beam->[$i],$Beam->[$i]->{'score'});
	}

	
	my($updatedParams);

	$i=0;
	while(! $reorderPQ->empty()) {
		my($obj,$priority) = $reorderPQ->pop_heap();

		$localbeam->[$i]->[0] = $priority;
		$localbeam->[$i]->[1] = $obj;
	}

	return $localbeam;
}


sub testNode2 {

	my($corpus) = shift;
	my($senNum) = shift;
	my($rootNode) = shift;
	my($Parameters) = shift;

	my($Varg,$Dep);
	my($engsen,$hinsen);
	my($GoldAlign,$GenAlign,$GenAlign2);
	my($Beam,$TempBeam);
	my($LFeatures,$score);
	my($localbeam,%localbeams);
	my($k,$m,$n,$p,$i);
	my($minScore,$minPosition);
	my($hinwordpos);
	my($verbnum,$argnum);
	my($GenFeatures);
	my($nengwords,$nhinwords);

	$Dep = $corpus->{$senNum}->{'SDep'};
	$engsen = $corpus->{$senNum}->{'SSen'};
	$nengwords = @{$engsen};
	$hinsen = $corpus->{$senNum}->{'TSen'};
	$nhinwords = @{$hinsen};
	$GoldAlign = $corpus->{$senNum}->{'Align'};

	$corpus->{$senNum}->{'AlignBeam'} = new AlignBeam($C{'K'});
	$Beam = $corpus->{$senNum}->{'AlignBeam'};


	my($s);

	my($obj,$priority);
	my(@srcNodes);

	my($child);
	foreach $child (@{$Dep->[$rootNode]->{'attch'}})
	{
		$corpus->testNode2($senNum,$child,$Parameters,$ifUpdate);
	}

#	print "Testing $senNum ($rootNode)\n";
	my(@srcNodes) = $corpus->getSrcNodes($senNum,$rootNode,0);
	my(@secondNodes) = $corpus->getSecondSrcNodes($senNum,\@srcNodes,$rootNode);
	push(@srcNodes,@secondNodes);
	my(@thirdNodes) = $corpus->getThirdSrcNodes($senNum,\@secondNodes,$rootNode);
	push(@srcNodes,@thirdNodes);

	$Beam = &getKBestAlignsKBestChildren($corpus,$senNum,$rootNode,\@srcNodes,$Parameters,$C{'K'});

	$subTreeAligns{$rootNode} = $Beam;

#	print $Beam->[0]->{'srcNode'}."\n";
#	print $Beam->[0]->{'localScore'}."\n";
#	$Beam->[0]->{'align'}->print($engsen);
#O$	my($predNum)=1;
#foreach $item (@$Beam) {
#		print "Prediction $predNum\n";
#		print "SrcNode = $item->{'srcNode'}\n";
#		print "Local Score = ".$item->{'localScore'}."\n";
#		$item->{'align'}->print($engsen);
#		$item->{'nodeFeats'}->print();
#		$predNum++;
#	}
#	print "--------\n";
}

sub predictAndupdatenode2
{
	my($corpus) = shift;
	my($senNum) = shift;
	my($nodeId) = shift;
	my($Parameters) = shift;
	my($ifUpdate) = shift;

	my($Varg,$Dep);
	my($engsen,$hinsen);
	my($GoldAlign,$GenAlign,$GenAlign2);
	my($Beam,$TempBeam);
	my($LFeatures,$score);
	my($localbeam,%localbeams);
	my($k,$m,$n,$p,$i);
	my($minScore,$minPosition);
	my($hinwordpos);
	my($verbnum,$argnum);
	my($GenFeatures);
	my($nengwords,$nhinwords);

	$Dep = $corpus->{$senNum}->{'SDep'};
	$engsen = $corpus->{$senNum}->{'SSen'};
	$nengwords = @{$engsen};
	$hinsen = $corpus->{$senNum}->{'TSen'};
	$nhinwords = @{$hinsen};
	$GoldAlign = $corpus->{$senNum}->{'Align'};

	$corpus->{$senNum}->{'AlignBeam'} = new AlignBeam($C{'K'});
	$Beam = $corpus->{$senNum}->{'AlignBeam'};

	my($s);

	#print STDERR "$senNum) words($nengwords):".scalar($nhinwords);
	#print "words($nengwords):".scalar($nhinwords)."\n";
	$starttime = time();

	my($obj,$priorIty);

	foreach $child (@{$Dep->[$nodeId]->{'attch'}})
	{
		$localbeams{$child} = $corpus->predictAndupdatenode2($senNum,$child,$Parameters,$ifUpdate);
		#print "CHILD = $child $localbeams{$child}...\n";
	}
		

	#Getting the Local beam of nodeId
	$localpq = new PQ;

	for($k=0;$k<=$nhinwords;$k++) # here K == nhinwords for src going to NULL
	{

		my @candwords;
		if($k!=$nhinwords)
		{ push(@candwords,$k); }

		my($LFeatures) = new Features;
		$LFeatures->getnodeLFeatures($nodeId,$engsen,$hinsen,\@candwords,"p");

		$score = $Parameters->getScore($LFeatures);

		#print "Alignment between $nodeId -> ".join('_',@candwords)." score=$score\n";
		#$LFeatures->print();

		$localpq->push_heap(\@candwords,$score);
	}

	for($k=0;$k<$nhinwords-1;$k++) {

		my @candwords;
		push(@candwords,$k); 
		push(@candwords,$k+1);

		my($LFeatures) = new Features;
		$LFeatures->getnodeLFeatures($nodeId,$engsen,$hinsen,\@candwords,"p");

		$score = $Parameters->getScore($LFeatures);

		#print "Alignment between $nodeId -> ".join('_',@candwords)." score = $score\n";
		#$LFeatures->print();

		$localpq->push_heap(\@candwords,$score);
	}

	
#	print "+++++++++Processing node $nodeId of Sentence $senNum+++++++++++++\n";
	# Get Top-K local parameters and their features in order to update
	my($PredLFeatArray);
	my($mistakesLArray);
	$localbeam = new LocalBeam($nhinwords);	
	$k=0;
	while(! $localpq->empty()) {
		my($obj,$priority) = $localpq->pop_heap();

		if($ifUpdate) {
			my($LFeatures) = new Features;

#			print "Updating parameters of Sentence $senNum node $nodeId (".join('-',@$obj).")\n";
			$LFeatures->getnodeLFeatures($nodeId,$engsen,$hinsen,$obj,"u");
#			$LFeatures->print();

			$PredLFeatArray->[$k] = $LFeatures;
			$mistakesLArray->[$k] = &getMistakes($GoldAlign->{'aln'}->[$nodeId],$obj);
#			print join('-',@{$GoldAlign->{'aln'}->[$nodeId]})." ".join('-',@$obj)."\n";

#			print "Mistakes = $mistakesLArray->[$k]\n";

		}
			
		$localbeam->[$k]->[0] = $priority;
		$localbeam->[$k]->[1] = $obj;
		$k++;

		if($k==$C{'K'}) {
			last;
		}
	}

	my($lK) = $k;
	my($reorderLPQ) = new PQ;

	# Update the local parameters and Re-score the local beam
	if($ifUpdate) {

#		print "GOLD Local Features - $nodeId\n";
#		$corpus->{$senNum}->{'nodeLFeatures'}->[$nodeId]->print();
#		print "Gold Score ==".$Parameters->getScore($corpus->{$senNum}->{'nodeLFeatures'}->[$nodeId])."\n";;

#		print "Updating Params ($lK)\n";

#		print "Updating Local Parameters $senNum $nodeId\n";
		$Parameters->updateParams($corpus->{$senNum}->{'nodeLFeatures'}->[$nodeId],$PredLFeatArray,$mistakesLArray,$lK);

#		print "New Gold Score ==".$Parameters->getScore($corpus->{$senNum}->{'nodeLFeatures'}->[$nodeId]);
#		print "Compute Final Scores Predicted Features ($lK) :\n";
		for($k=0;$k<$lK;$k++) {
			
			my($obj) = $localbeam->[$k]->[1];
			
			my($LFeatures) = new Features;
			$LFeatures->getnodeLFeatures($nodeId,$engsen,$hinsen,$obj,"u");

#			print "Num $k\n";
#			$LFeatures->print();
#			print "Score = ".$Parameters->getScore($LFeatures)."\n";

			my($priority) = $Parameters->getScore($LFeatures);

			$reorderLPQ->push_heap($obj,$priority);
		}

		$k=0;
		while(! $reorderLPQ->empty()) {
			my($obj,$priority) = $reorderLPQ->pop_heap();

			$localbeam->[$k]->[0] = $priority;
			$localbeam->[$k]->[1] = $obj;

			$k++;
		}
	}

	$localbeams{$nodeId} = $localbeam;

	my($globalPQ) = new PQ;

	my($oneAlign);
	my($onePriority);

	my(%insertedAligns) = ();
	my($insertedKey) = "";

	$onePriority = 0;
#	print "OneAlign: ";
	foreach $i (keys %localbeams)  #only the node and there children.
	{
		$oneAlign->{$i} = 0;
		$onePriority += $localbeams{$i}->[0]->[0];		

		$insertedKey.="0_";
	}

	$globalPQ->push_heap($oneAlign,$onePriority);
	$insertedKey=~s/_$//g;
	$insertedAligns{"$insertedKey"} = 1;

	$time = time();
	$duration = $time - $starttime;
	$starttime = $time;
	#print STDERR " init:$duration";

	my($newK);
	$newK = $C{'K'};

	for($k=0;$k<$C{'K'};$k++) 
	{

		my($oneAlign);
		if($globalPQ->empty()) {
			$newK = $k;
			last;
		}

		($oneAlign,$onePriority) = $globalPQ->pop_heap();

		#print "\n$onePriority: ".join(' ',%{$oneAlign})."\n";

		$GenAlign = $Beam->[$k];
		#print "$k $GenAlign\n";

		foreach $i (keys %localbeams) 
		{
			my($hn);
			if($i == $nodeId) 
			{
				foreach $hn (@{$localbeams{$i}->[$oneAlign->{$i}]->[1]}) #?????
				{
					$GenAlign->addalign($i,$hn);
				}
			}
			else 
			{
				#$localbeams{$i}->[$oneAlign->{$i}]->[1]->print($engsen);
				$GenAlign->mergealign($engsen,$localbeams{$i}->[$oneAlign->{$i}]->[1]);
			}
			#$GenAlign->print($engsen);
		}
		$GenAlign->{'score'} = $onePriority;
		


		
		
		# Put in the Global Beam

		foreach $i (keys %localbeams) {

			my(%newArr) = %{$oneAlign};
			my($newPriority);

			$newArr{$i} = $newArr{$i}+1;

			my($key);
			foreach $key (sort {$a<=>$b} keys %newArr) {
				$insertedKey = $newArr{$i}."_";    #?????????????????
			}
			$insertedKey =~s/_$//g;

			if(! $insertedAligns{"$insertedKey"}) {

				$newPriority = $onePriority + $localbeams{$nodeId}->[$newArr{$nodeId}]->[0] - $localbeams{$nodeId}->[$newArr{$nodeId}-1]->[0];
				$globalPQ->push_heap(\%newArr,$newPriority);
				$insertedAligns{"$insertedKey"} = 1;
			}
		}
	}



	my($reorderPQ) = new PQ;
	$corpus->{$senNum}->{'AlignBeam'} = $Beam;

	#-------------------------------Update Parameters:
	my $PredFeatArray;
	my $mistakesArray;
	my($obj,$priority);

#	print "SENTENCE $senNum\n";
	if($ifUpdate) {
#		print "GOLD other features :\n";
#		$corpus->{$senNum}->{'nodeOFeatures'}->[$nodeId]->print();
		
#		print "Predicted Other features :\n";
		for($i=0;$i<$newK;$i++) {
			my($Features) = new Features;
			$Features->getnodeOFeatures($nodeId,$engsen,$hinsen,$Dep,$Beam->[$i],"u");

#			$Features->print();

			$PredFeatArray->[$i] = $Features;
			$mistakeArray->[$i] = $GoldAlign->getnodeMistakes($nodeId,$Beam->[$i]);
		}

		$Parameters->updateParams($corpus->{$senNum}->{'nodeOFeatures'}->[$nodeId],$PredFeatArray,$mistakeArray,$newK);
	}

	for($i=0;$i<$newK;$i++) {

		my($Features) = new Features;
		$Features->getnodeOFeatures($nodeId,$engsen,$hinsen,$Dep,$Beam->[$i],"u");

		$score = $Parameters->getScore($Features);

		$reorderPQ->push_heap($Beam->[$i],$Beam->[$i]->{'score'}+$score);
	}
	
	my($localbeam);

	$localbeam = new LocalBeam($newK);


#	print "================ K-Best for Node $nodeId ===========================\n";
	#$corpus->{$senNum}->{'SFeatures'}->print();
#	$corpus->{$senNum}->{'Align'}->print($engsen);
	#print "Predictions..\n";
#	print "$senNum , Gold Features of $nodeId\n";
#	$corpus->{$senNum}->{'nodeFeatures'}->[$nodeId]->print();
	
#	print "++++ Predicted Features : \n+++++";
	$i=0;

	while(! $reorderPQ->empty()) {
		($obj,$priority) = $reorderPQ->pop_heap();

		$localbeam->[$i]->[0] = $priority;
		$localbeam->[$i]->[1] = $obj;

		$i++;
	}

	#print "Before $senNum...\n";
	#$Parameters->list();
	my($updatedParams);

	return $localbeam;
}

sub getMistakes {
	my($goldarray) = $_[0];
	my($comparray) = $_[1];

	my($correct) = 0;
	my($total) = 0;
	my($mistakes) = 0;
	my($i,$j);

	my $flag = 0;

	if(@$goldarray==0) {
		if(@$comparray==0) {
			return 0;
		}
		else {
			return 1;
		}
	}

	foreach $goldWord (@$goldarray) {
		my $flag = 0;
		foreach $predWord (@$comparray) {
			$flag = 1 if($goldWord == $predWord);
		}
		if($flag==0) {
			$mistakes++;
		}
	}

	foreach $predWord (@$comparray) {
		my $flag = 0;
		foreach $goldWord (@$goldarray) {
			$flag = 1 if($goldWord == $predWord);
		}
		if($flag==0) {
			$mistakes++;
		}
	}


	return $mistakes/(@$comparray+@$goldarray);

	
}

sub getDecoderLists
{
	my($corpus) = shift;
	my($Parameters) = shift;
	my($dictFile) = shift;
	my($numDict) = shift;
	my($fromAlign) = shift;

	my($Varg,$Dep);
	my($engsen,$hinsen);
	my($GoldAlign,$GenAlign,$GenAlign2);
	my($Beam,$TempBeam);
	my($LFeatures,$score);
	my($localbeam,%localbeams);
	my($k,$m,$n,$p,$i);
	my($minScore,$minPosition);
	my($hinwordpos);
	my($verbnum,$argnum);
	my($LFeatures,$GenFeatures);
	my($nengwords,$nhinwords);
	my($entries,$prob);

	if(-e $dictFile) {
		open(DICT,"$dictFile");
		while($dictEntry=<DICT>) {
			chomp($dictEntry);
			($engForm,$hinForm,$score) = split(/\s+/,$dictEntry);
			push(@{$entries->{$engForm}},$hinForm);
			push(@{$probs->{$engForm}},$score);
		}
		close(DICT);
	}

	foreach $senNum (sort {$a<=>$b} keys %$corpus) {

		print "$senNum...\n";

		$Dep = $corpus->{$senNum}->{'SDep'};
		$engsen = $corpus->{$senNum}->{'SSen'};
		$nengwords = @{$engsen};
		$hinsen = $corpus->{$senNum}->{'TSen'};
		$nhinwords = @{$hinsen};
		$GenAlign = $corpus->{$senNum}->{'AlignBeam'}->[0];

		print $GenAlign."\n";;

		my($s);

		#print STDERR "$senNum) words($nengwords):".scalar($nhinwords);
		#print "words($nengwords):".scalar($nhinwords)."\n";
		$starttime = time();

		my($obj,$priorIty);

		#print scalar(@$engsen)." ".scalar(@$hinsen)."\n";
#		print "ENGSEN: ";
#		for($i=0;$i<@$engsen;$i++) {
#			print $engsen->[$i]->{'word'}." ";
#		}
#		print "\nHINSEN: ";
#			for($i=0;$i<@$hinsen;$i++) {
#			print $hinsen->[$i]->{'word'}." ";
#		}
#		print "\n\n";

		#Getting the Local beam of nodeId
		for($nodeId=0;$nodeId<=$nengwords;$nodeId++) {

			if($fromAlign) {

				my @candwords;
				push(@candwords,sort @{$GenAlign->{'aln'}->[$nodeId]});

				$LFeatures = new Features;
				$LFeatures->getnodeLFeatures($nodeId,$engsen,$hinsen,\@candwords,"p");
				$score = $Parameters->getScore($LFeatures);

				($engForm,$hinForm) = &getLCanonicalForm($nodeId,$engsen,$hinsen,\@candwords);

				#print "$engForm,$hinForm\n";
				if(&existsArray(@{$entries->{$engForm}},$hinForm) || $engForm eq "" || $hinForm eq "") {
						next; 
				}

				if($#{$probs->{$engForm}}!=-1) {
					for($p=$#{$probs->{$engForm}};$p>=0;$p--) {
						if($score>$probs->{$engForm}->[$p]) {
							splice(@{$entries->{$engForm}},$p,0,$hinForm);
							splice(@{$probs->{$engForm}},$p,0,$score);
							if(@{$probs->{$engForm}}>$numDict) {
								pop(@{$probs->{$engForm}});
								pop(@{$entries->{$engForm}});
							}
							last;
						}
					}
				}
				else {
					$entries->{$engForm}->[0] = $hinForm;
					$probs->{$engForm}->[0] = $score;
				}
			}
			else {


			for($k=0;$k<=$nhinwords;$k++) # here K == nhinwords for src going to NULL
			{
	
				my($canonicalForm);
				my @candwords;
				if($k!=$nhinwords)
				{ push(@candwords,$k); }

				$LFeatures = new Features;
				$LFeatures->getnodeLFeatures($nodeId,$engsen,$hinsen,\@candwords,"p");
				$score = $Parameters->getScore($LFeatures);

				($engForm,$hinForm) = &getLCanonicalForm($nodeId,$engsen,$hinsen,\@candwords);

				#print "$engForm,$hinForm\n";
				if(&existsArray(@{$entries->{$engForm}},$hinForm) || $engForm eq "" || $hinForm eq "") {
						next; 
				}

				if($#{$probs->{$engForm}}!=-1) {
					for($p=$#{$probs->{$engForm}};$p>=0;$p--) {
						if($score>$probs->{$engForm}->[$p]) {
							splice(@{$entries->{$engForm}},$p,0,$hinForm);
							splice(@{$probs->{$engForm}},$p,0,$score);
							if(@{$probs->{$engForm}}>$numDict) {
								pop(@{$probs->{$engForm}});
								pop(@{$entries->{$engForm}});
							}
							last;
						}
					}
				}
				else {
					$entries->{$engForm}->[0] = $hinForm;
					$probs->{$engForm}->[0] = $score;
				}

				#print scalar(@{$probs->{$engForm}})."\n";
			}

			for($k=0;$k<$nhinwords-1;$k++) {
	
				my @candwords;
				push(@candwords,$k); 
				push(@candwords,$k+1);

				$LFeatures = new Features;
				$LFeatures->getnodeLFeatures($nodeId,$engsen,$hinsen,\@candwords,"p");
				$score = $Parameters->getScore($LFeatures);

				($engForm,$hinForm) = &getLCanonicalForm($nodeId,$engsen,$hinsen,\@candwords);

				# if(&existsArray(@{$entries->{$engForm}},$hinForm)) {
				if(&existsArray(@{$entries->{$engForm}},$hinForm) || $engForm eq "" || $hinForm eq "") {
						next; 
				}
	
				if($#{$probs->{$engForm}}!=-1) {
					for($p=$#{$probs->{$engForm}};$p>=0;$p--) {
						if($score>$probs->{$engForm}->[$p]) {
							splice(@{$entries->{$engForm}},$p,0,$hinForm);
							splice(@{$probs->{$engForm}},$p,0,$score);
							if(@{$probs->{$engForm}}>$numDict) {
								pop(@{$probs->{$engForm}});
								pop(@{$entries->{$engForm}});
							}
							last;
						}
					}
				}
				else {
					$entries->{$engForm}->[0] = $hinForm;
					$probs->{$engForm}->[0] = $score;
				}

				#print scalar(@{$probs->{$engForm}})."\n";
			}
			}
		}
	}

	open(DICT,">$dictFile");
	foreach $engForm (keys %$entries) {
		for($p=0;$p<@{$entries->{$engForm}};$p++) {
			print DICT $engForm."\t".$entries->{$engForm}->[$p]."\t".$probs->{$engForm}->[$p]."\n";
		}
	}
	close(DICT);
		
}

sub getLCanonicalForm {
	my($nodeId,$engsen,$hinsen,$tgtwords) = @_;
	my($engword) = $engsen->[$nodeId]->{'word'};
	my($hinwords,$i);


	foreach $i (@$tgtwords) {
		$hinwords.=$hinsen->[$i]->{'word'}."_";
	}
	$hinwords=~s/_$//g;
	return ($engword,$hinwords);
}

sub decodenode {

	my($corpus) = shift;
	my($senNum) = shift;
	my($nodeId) = shift;
	my($Parameters) = shift;
	my($dictionary) = shift;

	my($Varg,$Dep);
	my($engsen,$hinsen);
	my($GoldAlign,$GenAlign,$GenAlign2);
	my($Beam,$TempBeam,$bagBeam);
	my($LFeatures,$score);
	my($localbeam,%localbeams);
	my($k,$m,$n,$p,$i);
	my($minScore,$minPosition);
	my($hinwordpos);
	my($verbnum,$argnum);
	my($LFeatures,$GenFeatures);
	my($nengwords,$nhinwords);

	$Dep = $corpus->{$senNum}->{'SDep'};
	$engsen = $corpus->{$senNum}->{'SSen'};
	$nengwords = @{$engsen};

	my($engword) = $engsen->[$nodeId]->{'word'};
	#print "----->".keys(%{$engsen->[$nodeId]})." ".$engword."\n";

	#$hinsen = $corpus->{$senNum}->{'TSen'};
	#$nhinwords = @{$hinsen};
	#$GoldAlign = $corpus->{$senNum}->{'Align'};

	# Possible Translations of this node are recorded here
	my(%transNode) = %{$dictionary->{$engword}};
	my(@hinwords) = keys %transNode;
	$nhinwords = @hinwords;

	#$corpus->{$senNum}->{'StringBeam'} = new StringBeam($C{'K'});
	#$Beam = $corpus->{$senNum}->{'StringBeam'};

	my($s);

	#print STDERR "$senNum) words($nengwords):".scalar($nhinwords);
	#print "words($nengwords):".scalar($nhinwords)."\n";
	$starttime = time();

	my($obj,$priorIty);


	#Getting the Local beam of nodeId
	$localpq = new PQ;

	#print "Translating $engword ($senNum, $nodeId) ...\n";
	if($nhinwords==0) {
		$nhinwords++;
		push(@hinwords,$engword);
	}
	
	foreach $hinword (@hinwords) 
	{
		$score = $transNode{$hinword};

		$localpq->push_heap($hinword,$score);
		#	print "\t\t$hinword ($score)\n";

	}

	$localbeam = new LocalBeam($nhinwords);	
	$k=0;
	while((!$localpq->empty()) && $k<$C{'K'}) {

		($obj,$priority) = $localpq->pop_heap();

		$localbeam->[$k]->[0] = $priority;
		$localbeam->[$k]->[1] = $obj;
		$k++;
	}

	$localbeams{$nodeId} = $localbeam;

	foreach $child (@{$Dep->[$nodeId]->{'attch'}})
	{
		$localbeams{$child} = $corpus->decodenode($senNum,$child,$Parameters,$dictionary);
		#print "CHILD = $child $localbeams{$child}...\n";
	}

	print STDERR "Tranlating $engword($nodeId)\n";
	
	my($globalPQ) = new PQ;

	my($oneAlign);
	my($onePriority);

	my(%insertedAligns,$insertedKey) = ();

	#print "Number of strings :";
	$onePriority = 0;
	foreach $i (keys %localbeams)  #only the node and there children.
	{
		$oneAlign->{$i} = 0;
		$onePriority += $localbeams{$i}->[0]->[0];		
		#print " Node-$i:".scalar(@{$localbeams{$i}});
		
		$insertedKey.="0_";
	}
	#print "\n";

	#print "Best score = $onePriority\n";


	$globalPQ->push_heap($oneAlign,$onePriority);
	$insertedKey =~s/_$//g; 
	$insertedAligns{"$insertedKey"} = 1;

	$time = time();
	$duration = $time - $starttime;
	$starttime = $time;
	#print STDERR " init:$duration";

	my($newK);
	$newK = $C{'K'};

	my($oneBag);
	for($k=0;$k<$C{'K'};$k++) 
	{

		my($oneAlign);
		if($globalPQ->empty()) {
			$newK = $k;
			last;
		}

		($oneAlign,$onePriority) = $globalPQ->pop_heap();

		#print "\n$onePriority: ".join(' ',%{$oneAlign})."\n";

		my(%bagHash) = ();
		$bagBeam->[$k] = \%bagHash;

		$oneBag = $bagBeam->[$k];
		#print "$k $GenAlign\n";

		$totalNodes = 0;
		foreach $i (keys %localbeams) 
		{
			my($hn);
			
			$oneBag->{'string'}->{$i} = $localbeams{$i}->[$oneAlign->{$i}]->[1];

			$totalNodes++;
			#print "$oneBag->{'string'}->{$i},(($bagBeam->[$k])), ";
		}
		#print "\n";

		# Compute strings per node

		$oneBag->{'score'} = $onePriority;
		#print "Score = $oneBag->{'score'}\n";


		# Put in the Global Beam

		foreach $i (keys %localbeams) {

			my(%newArr) = %{$oneAlign};
			my($newPriority);

			$newArr{$i} = $newArr{$i}+1;
			if(!$localbeams{$i}->[$newArr{$i}]->[1]) {
				next;
			}

			my($key);
			foreach $key (sort {$a<=>$b} keys %newArr) {
				$insertedKey .= $newArr{$key}."_";
			}
			$insertedKey =~s/_$//g;

			if(! $insertedAligns{"$insertedKey"}) {

				$newPriority = $onePriority + $localbeams{$i}->[$newArr{$i}]->[0] - $localbeams{$i}->[$newArr{$i}-1]->[0];
				$globalPQ->push_heap(\%newArr,$newPriority);
				$insertedAligns{"$insertedKey"} = 1;
			}
		}
	}


	#print "\tBags of Strings (num=$newK)\n";
	
	my($stringPQ) = new PQ;
	my($finalPQ) = new PQ;

	#print "\t IDs of Nodes-> ".join(' * ',keys %{$oneBag->{'string'}})."\n";
#        for($k=0;$k<$newK;$k++) {
#               my($oneBag) = $bagBeam->[$k];
#               my($oneScore) = $oneBag->{'score'};

#		print "\t $k) ".join(' * ',values %{$oneBag->{'string'}})." : $oneScore\n";
#	}


	my(%checkedStruct) = ();
	my(%checkedString) = ();

	for($k=0;$k<$newK;$k++) {

		my($oneBag) = $bagBeam->[$k];
		my($oneScore) = $oneBag->{'score'};

		my($initialHypo);
		$initialHypo->{'translation'} = $oneBag->{'string'}->{$nodeId};
		$initialHypo->{'translatedNodes'}->[0] = $nodeId;
		$initialHypo->{'bagScr'} = $oneScore;
		$initialHypo->{'lmScr'} = &lmscore($initialHypo->{'translation'},$Parameters->{'lm'});
		$initialHypo->{'synScr'} = 0;
		$initialHypo->{'score'} = &totalHypoScr($initialHypo);

		$checkedStringr{"$initialHypo->{'translation'}"} = $initialHypo->{'lmScr'};
		#print "Initial LM score of Root : $initialHypo->{'lmScr'}\n";

#		print "Intial Hypo ::\n";
		&printHypo($initialHypo);

		$hypoPQ[0] = new PQ;
		$hypoPQ[0]->push_heap($initialHypo,$initialHypo->{'score'});

		my($numChildren) = scalar(keys %localbeams) - 1;
		for($t=1;$t<=$numChildren;$t++) {
			$hypoPQ[$t] = new PQ;

#			print "Child Number $t\n";
			
			for($r=1;$r<=$newK && !$hypoPQ[$t-1]->empty();$r++) {

				my($hypo,$hyposcr) = $hypoPQ[$t-1]->pop_heap();	

				@succHypo = &getSucchypo($hypo,$oneBag);
				my($newHypo);
				foreach $newhypo (@succHypo) {


					my($synky) = join(' ',@{$newhypo->{'translatedNodes'}});
					my($lmky) = $newhypo->{'translation'};

					if(defined $checkedStruct{$synky} && defined $checkedString{$lmky}) { next;}

					if(!defined $checkedString{$lmky}) {
						$checkedString{$lmky} = &lmscore($lmky,$Parameters->{'lm'});
						#print "New LM: $lmky\n";
						#print " Score: $checkedString{$lmky}\n";
					}

					if(!defined $checkedStruct{$synky}) {

						my($Features) = new Features;
						my($hinsen);
						my($Align) = new Align;
						my(%alignedNodes);

						for($q=0;$q<=$#{$newhypo->{'translatedNodes'}};$q++) {
							my($srcNode) = $newhypo->{'translatedNodes'}->[$q];
							$hinsen->[$q]->{'word'} = $srcNode;
							$Align->addalign($srcNode,$q);

							$alignedNodes{$srcNode} = 1;
						}
						
						foreach $i (keys %{$oneBag->{'string'}}) {
							if(!$alignedNodes{$i}) {
								$Align->addalign($i,"X");
							}
						}

						#print "Alignments\n";
						#$Align->print($engsen);

						#print "Get Syntactic Features for node $nodeId\n";

						#print "Structure: ".$synky."\n";
#						$Features->getnodeSynFeatures($nodeId,$engsen,$hinsen,$Dep,$Align,"p");
#						foreach $feat (keys %$Features) {
#							print "FEAT : $feat\n";
#						}

						$checkedStruct{$synky} = $Parameters->getScore($Features);
#						print " Score: $checkedStruct{$synky}\n";
					}

					$newhypo->{'synScr'} = $checkedStruct{$synky};
					$newhypo->{'lmScr'} = $checkedString{$lmky};

					$newhypo->{'score'} = &totalHypoScr($newhypo);

#					print "New Hypo's :";
#					&printHypo($newhypo);

					$hypoPQ[$t]->push_heap($newhypo,$newhypo->{'score'});	
				}
			}
		}

		#print " $k>> FINAL HYPOTHESES\n";
		while(!$hypoPQ[$numChildren]->empty()) {
			my($hypo,$hyposcr) = $hypoPQ[$numChildren]->pop_heap();
			#&printHypo($hypo);
			$stringPQ->push_heap($hypo,$hyposcr);	
		}
	}

=cut
	print "\n\tBest LM Hypothesis ($newK) ::\n";
	for($r=1;$r<=$newK && !$finalPQ->empty();$r++) {
		my($hypo,$hyposcr) = $finalPQ->pop_heap();

		&printHypoLn($hypo,1);

		my($Features) = new Features;

		my($hinsen);
		my($Align) = new Align;

		for($q=0;$q<=$#{$hypo->{'translatedNodes'}};$q++) {
			my($srcNode) = $hypo->{'translatedNodes'}->[$q];
			$hinsen->[$srcNode]->{'word'} = $srcNode;
			$Align->addalign($srcNode,$q);
		}
		$Align->print($engsen);
			
		print "Get Syntactic Features for node $nodeId\n";
	$Features->getnodeSynFeatures($nodeId,$engsen,$hinsen,$Dep,$Align,"p");
		foreach $feat (keys %$Features) {
			print "FEAT : $feat\n";
		}

		$hypo->{'synScr'} = $Parameters->getScore($Features);
		#my($hyposcr) = $hyposcr * $Parameters->{'lm'} + $Parameters->getScore($Features);
		$hypo->{'score'} = &totalHypoScr($hypo);

		$stringPQ->push_heap($hypo,$hypo->{'score'});
	}
=cut

	$k=0;
	
	# print "K-Best for Node $nodeId\n";
	#print "\n\tFINAL BEST ::\n";

	$flocalbeam = new LocalBeam($newK);
	
	while(! $stringPQ->empty()) {

		if($k==$newK) { last; }
		
		($obj,$priority) = $stringPQ->pop_heap();
		#&printHypoLn($obj,1);

		$flocalbeam->[$k]->[0] = $priority;
		$flocalbeam->[$k]->[1] = $obj->{'translation'};

		$k++;
	}
	#print "----------------------------\n";

	return $flocalbeam;
}

sub printHypo {
	my($hypo) = $_[0];
	print "----------------------------\n";
	print "| Trans: $hypo->{'translation'}\n";
	print "| Nodes: ".join(' ',@{$hypo->{'translatedNodes'}})."\n";
	print "| score: ($hypo->{'bagScr'},$hypo->{'lmScr'},$hypo->{'synScr'}) = $hypo->{'score'}\n";
	print "----------------------------\n\n";
}

sub printHypoLn {
	my($hypo) = $_[0];
	my($tabs) = $_[1];

	my($tb);
	for($tb=1;$tb<=$tabs;$tb++) {
		print "\t";
	}
	
	print "$hypo->{'translation'}\t($hypo->{'bagScr'},$hypo->{'lmScr'},$hypo->{'synScr'}) = $hypo->{'score'}\n";
}


sub totalHypoScr {
	my($hypo) = $_[0];
	return $hypo->{'bagScr'} + $hypo->{'synScr'} + $hypo->{'lmScr'};
}

sub getSucchypo {
	my($hypo,$oneBag);
	my($lmWeight);
	my(@newhypos);
	my($i);
	$hypo = $_[0];
	$oneBag = $_[1];
	$lmWeight = $_[2];
	
	foreach $i (keys %{$oneBag->{'string'}}) {
		if(!&existsArray($hypo->{'translatedNodes'},$i)) {
			my($hypo1,$hypo2);
			$hypo1 = &copyHypo($hypo);
			
			$hypo1->{'translation'} = $oneBag->{'string'}->{$i}."_".$hypo1->{'translation'};
			unshift(@{$hypo1->{'translatedNodes'}},$i);
			$hypo1->{'lmScr'} = 0;
			$hypo1->{'score'} = &totalHypoScr($hypo1);
			push(@newhypos,$hypo1);
			
			$hypo2 = &copyHypo($hypo);

			$hypo2->{'translation'} = $hypo2->{'translation'}."_".$oneBag->{'string'}->{$i};
			push(@{$hypo2->{'translatedNodes'}},$i);
			$hypo2->{'lmScr'} = 0;
			$hypo2->{'score'} = &totalHypoScr($hypo2);
			push(@newhypos,$hypo2);
		}
	}
	return @newhypos;
}

sub lmscore {

	my($string);
	$string = $_[0];
	$weight = $_[1];

	open(TMP,">/tmp/lmstring.$$.txt");
	$string=~s/^\s*//g; $string=~s/\s*$//g; $string=~s/_+/ /g;
	print TMP $string;
	close(TMP);

	my(@words) = split(/\s+/,$string);
	if(@words==0) {
		return 0;
	}
	
	my($lmscore) = `./scripts/string2fst2.pl < /tmp/lmstring.$$.txt | fsmcompile -i ~/corpus/hnd_50k.txt.wl | fsmcompose ~/corpus/hnd_50k-5k.txt.lm.fst - | fsmrmepsilon | fsmbestpath | fsmprint -i ~/corpus/hnd_50k.txt.wl | ./scripts/getlmscore.pl`;
	chomp($lmscore);

	return $weight*$lmscore/scalar(@words);

}

sub copyHypo {
	my($hypoTgt,$hypoSrc);
	my($nodeIndex);
	$hypoSrc = $_[0];


	$hypoTgt->{'translation'} = $hypoSrc->{'translation'};
	for($nodeIndex=0;$nodeIndex<@{$hypoSrc->{'translatedNodes'}};$nodeIndex++) {
		$hypoTgt->{'translatedNodes'}->[$nodeIndex] = $hypoSrc->{'translatedNodes'}->[$nodeIndex];
	}
	$hypoTgt->{'bagScr'} = $hypoSrc->{'bagScr'};
	$hypoTgt->{'lmScr'} = $hypoSrc->{'lmScr'};
	$hypoTgt->{'synScr'} = $hypoSrc->{'synScr'};
	$hypoTgt->{'score'} = $hypoSrc->{'score'};

	return $hypoTgt;
}

sub existsArray {
	my($arrayRef,$element,$arrayElement);
	$arrayRef=$_[0];
	$element = $_[1];
	$arrayElement = $_[2];

	foreach $arrayElement (@{$arrayRef}) {
		if($arrayElement == $element) {
			return 1;
		}
	}
	return 0;
}

sub predictAndupdate1 {

	my($corpus) = shift;
	my($senNum) = shift;
	my($Parameters) = shift;
	my($ifUpdate) = shift;
	my($i);

	my($Varg,$Dep);
	my($engsen,$hinsen);
	my($GoldAlign,$GenAlign,$GenAlign2);
	my($Beam,$TempBeam);
	my($LFeatures,$score);
	my($localbeam,%localbeams);
	my($k,$m,$n,$p,$i);
	my($minScore,$minPosition);
	my($hinwordpos);
	my($verbnum,$argnum);
	my($LFeatures,$GenFeatures);
	my($nengwords,$nhinwords);

	$Dep = $corpus->{$senNum}->{'SDep'};
	$engsen = $corpus->{$senNum}->{'SSen'};
	$nengwords = @{$engsen};
	$hinsen = $corpus->{$senNum}->{'TSen'};
	$nhinwords = @{$hinsen};
	$GoldAlign = $corpus->{$senNum}->{'Align'};

	$corpus->{$senNum}->{'AlignBeam'} = new AlignBeam($C{'K'});
	$Beam = $corpus->{$senNum}->{'AlignBeam'};

	my($s);

#	print STDERR "$senNum) words($nengwords):".scalar($nhinwords);
	#print "words($nengwords):".scalar($nhinwords)."\n";
	$starttime = time();

	my($obj,$priority);
	for($i=0;$i<$nengwords;$i++)
	{
		$localpq = new PQ;


		for($k=0;$k<=$nhinwords;$k++) {

			my @candwords;
			if($k!=$nhinwords)
			{ push(@candwords,$k); }

			$LFeatures = new Features;
			$LFeatures->getnodeLFeatures($i,$engsen,$hinsen,\@candwords,"p");

			$score = $Parameters->getScore($LFeatures);

#			print "Alignment between $i -> ".join('_',@candwords)." score=$score\n";
#			$LFeatures->print();

			$localpq->push_heap(\@candwords,$score);
		}

		for($k=0;$k<$nhinwords-1;$k++) {

			my @candwords;
			push(@candwords,$k); 
			push(@candwords,$k+1);

			$LFeatures = new Features;
			$LFeatures->getnodeLFeatures($i,$engsen,$hinsen,\@candwords,"p");

			$score = $Parameters->getScore($LFeatures);

#			print "Alignment between $i -> ".join('_',@candwords)." score = $score\n";
#			$LFeatures->print();

			$localpq->push_heap(\@candwords,$score);
		}

		$localbeam = new LocalBeam($nhinwords);	
		$k=0;
		while(! $localpq->empty()) {
			($obj,$priority) = $localpq->pop_heap();

#			if($i==0) {
#				print "$priority ".join('_',@{$obj})."\n";
#			}

			$localbeam->[$k]->[0] = $priority;
			$localbeam->[$k]->[1] = $obj;
			$k++;
		}

		$localbeams{$i} = $localbeam;
	}		

	$time = time();
	$duration = $time - $starttime;
	$starttime = $time;
#	print STDERR " sort:$duration";

	my($globalPQ) = new PQ;

	my($oneAlign);
	my($onePriority);

	my(%insertedAligns,$insertedKey) = ();

	$onePriority = 0;
	foreach $i (keys %localbeams)
	{
		$oneAlign->{$i} = 0;
		$onePriority += $localbeams{$i}->[0]->[0];		
	}

	$globalPQ->push_heap($oneAlign,$onePriority);
	$insertedKey = join('_',keys %{$oneAlign});
	$insertedAligns{"$insertedKey"} = 1;

	$time = time();
	$duration = $time - $starttime;
	$starttime = $time;
#	print STDERR " init:$duration";

	my($newK);
	$newK = $C{'K'};

	for($k=0;$k<$C{'K'};$k++) {
		
		my($oneAlign);
		if($globalPQ->empty()) {
			$newK = $k;
			last;
		}

		($oneAlign,$onePriority) = $globalPQ->pop_heap();

		#print "\n$onePriority: ".join(' ',%{$oneAlign})."\n";

		$GenAlign = $Beam->[$k];
		#print "$k $GenAlign\n";
		foreach $i (keys %localbeams) {
			my($hn);
			foreach $hn (@{$localbeams{$i}->[$oneAlign->{$i}]->[1]}) {
				$GenAlign->addalign($i,$hn);
			}
		}
		$GenAlign->{'score'} = $onePriority;
		#print "Score $onePriority\n";

		# Put in the Global Beam

	       foreach $i (keys %localbeams) {

			my(%newArr) = %{$oneAlign};
			my($newPriority);

			$newArr{$i} = $newArr{$i}+1;

			my($key);
			foreach $key (sort {$a<=>$b} keys %newArr) {
				$insertedKey = $newArr{$i}."_";
			}
			$insertedKey =~s/_$//g;

			if(! $insertedAligns{"$insertedKey"}) {

				$newPriority = $onePriority + $localbeams{$i}->[$newArr{$i}]->[0] - $localbeams{$i}->[$newArr{$i}-1]->[0];
				$globalPQ->push_heap(\%newArr,$newPriority);
				$insertedAligns{"$insertedKey"} = 1;
			}
		}

	}


	$time=time();
	$duration = $time - $starttime;
	$starttime = $time;
#	print STDERR " kbest:$duration";

	$corpus->{$senNum}->{'Align'}->{'score'} = $Parameters->getScore($corpus->{$senNum}->{'SFeatures'});


	my($reorderPQ) = new PQ;

	$corpus->{$senNum}->{'AlignBeam'} = $Beam;
	
	# Recalculate the scores
	#print "Final Scores\n";
	$GenAlign = new Align($nengwords);
	#print "Alignments in the Global Beams\n";


	for($i=0;$i<$newK;$i++)
	{
		$Features = new Features;
		$Features->getsenFeatures($engsen,$hinsen,$Dep,$Beam->[$i],"u");
		
		$Beam->[$i]->{'score'} = $Parameters->getScore($Features);

		$reorderPQ->push_heap($Beam->[$i],$Beam->[$i]->{'score'});
	}

	$time = time();
	$duration = $time - $starttime;
	$starttime = $time;
#	print STDERR " reranking-pushheap:$duration";

	my($obj,$priority);

	my $PredFeatArray;
	my $mistakesArray;

	$i=0;
	
	#print "K-Best for Sentence $senNum\n";
#	print "GOLD FEATURES & ALIGNMENT\n";
#	$corpus->{$senNum}->{'SFeatures'}->print();
#	$corpus->{$senNum}->{'Align'}->printAln($engsen,$hinsen);
#	for($nodeId=0;$nodeId<@$engsen;$nodeId++) {
#		my($Feat) = new Features;
#		$Feat->getnodeFeatures($nodeId,$engsen,$hinsen,$Dep,$GoldAlign,"p");
#		print "Node $engsen->[$nodeId]->{'word'} features..\n";
#		$Feat->print();
#		print "---\n";
#	}
	
	#print "Predictions..\n";
	while(! $reorderPQ->empty()) {
		($obj,$priority) = $reorderPQ->pop_heap();

		#print "$i) $priority\n";
		$Beam->[$i] = $obj;
		#$Beam->[$i]->print($engsen);

		if($ifUpdate) {
			$Features = new Features;
			$Features->getsenFeatures($engsen,$hinsen,$Dep,$Beam->[$i],"u");

			#$Features->print();

			$PredFeatArray->[$i] = $Features;
			$mistakeArray->[$i] = $GoldAlign->getMistakes($Beam->[$i]);

			#print "Mistakes = $mistakeArray->[$i]\n";
		}
		$i++;
	}

#	print "---------------------\n";
#	print "BEST PREDICTIONS ...\n";
#	$PredFeatArray->[0]->print();
#	$Beam->[0]->printAln($engsen,$hinsen);
#	for($nodeId=0;$nodeId<@$engsen;$nodeId++) {
#		my($Feat) = new Features;
#		$Feat->getnodeFeatures($nodeId,$engsen,$hinsen,$Dep,$Beam->[0],"p");
#		print "Node $engsen->[$nodeId]->{'word'} features..\n";
#		$Feat->print();
#		print "---\n";
#	}

#	print "---------------------\n";
#


	#print "Before $senNum...\n";
	#$Parameters->list();
	my($updatedParams);

	$Parameters->updateParams($corpus->{$senNum}->{'SFeatures'},$PredFeatArray,$mistakeArray,$newK) if($ifUpdate);
	#print "After $senNum...\n";
	#$Parameters->list();

#	print "New Gold Score = ".$Parameters->getScore($corpus->{$senNum}->{'SFeatures'})."\n";;
#	print "New Pred0 Score = ".$Parameters->getScore($PredFeatArray->[0])."\n\n";

	$time = time();
	$duration = $time - $starttime;
	$starttime = $time;
#	print STDERR " reranking-popheap:$duration\n";


	#print "Printing Beam in the final state\n";
	#for($i=0;$i<$C{'K'};$i++)
	#{
	#	$Beam->[$i]->print($corpus->{$senNum}->{'SSen'});
	#}
	#print "Done\n\n\n";
	
	return ($newK,$updatedParams);
}

sub updateparams {
	my($this) = shift;
	my($Parameters) = shift;
	my($j) = shift;
	my($K) = shift;
	my($updateoption) = shift;

	my(@b,$lam_dist,@dist);
	my($k);	
	my($Align,$GenAlign);
	my($Features,$GFeatures,$GenFeatures,$GenFeatures2);
	my($gscore) ;
	my(@alpha);

	$Align = $this->[$j]->{'Align'};
	$Varg = $this->[$j]->{'Varg'};
	$Dep = $this->[$j]->{'SDep'};
	$engsen = $this->[$j]->{'SSen'};
	$hinsen = $this->[$j]->{'TSen'};
	$GoldAlign = $this->[$j]->{'Align'};
	$Beam = $this->[$j]->{'AlignBeam'};

	$Features = $this->[$j]->{'Features'};
	$GFeatures = $this->[$j]->{'GFeatures'};
	$gscore = $Parameters->getScore($Features);

	for($k=0;$k<$K;$k++)
	{
		$GenAlign = $Beam->[$k];
		$GenFeatures = new Features;
		$GenFeatures2 = new Features;

		if($updateoption eq "a")
		{ 
			$GenFeatures->getFeatures($engsen,$hinsen,$GenAlign,$Varg,$Dep); 
			$GenFeatures2->difffeatures($Features,$GenFeatures);
		}
		else
		{ 
			$GenFeatures->getGFeatures($engsen,$hinsen,$GenAlign,$Varg,$Dep); 
			$GenFeatures2->difffeatures($GFeatures,$GenFeatures);
		}

=cut
		foreach $feat (keys %{$GenFeatures}) {
			print "$feat($GenFeatures->{$feat}) ";
		}
		print "\n";

		foreach $feat (keys %{$GenFeatures2}) {
			print "$feat($GenFeatures2->{$feat}) ";
		}
		print "\n\n";
=cut
		
		$lam_dist[$k] = $gscore - $this->[$j]->{'AlignBeam'}->[$k]->{'score'};
		$b[$k] = $Align->getMistakes($GenAlign);
		$b[$k] -= $lam_dist[$k];	
	
		$dist[$k] = $GenFeatures2;

		$b[$k] -= $lam_dist[$k];
		#print "B array = $b[$k]\n";
	}

	@alpha = &hildreth($K,\@dist,\@b);

	for($k=0;$k<$K;$k++)
	{
		$GenFeatures = $dist[$k];
		foreach $feat (keys %$GenFeatures)
		{
			$Parameters->{$feat} += $alpha[$k]*$GenFeatures->{$feat};
		}
	}
}

sub hildreth {
	my($K) = shift;
	my($a) = shift;
	my($b) = shift;

	my($i);
	my($max_iter) = 10000;
	my($eps) = 0.00000001;
	my($zero) = 0.000000000001;

	my(@alpha,@F,@kkt);
	my($max_kkt) = -1000000;

	my(@A);
	my(@is_computed);

	for($i=0;$i<$K;$i++)
	{
		$A[$i][$i] = Features::dotProduct($a->[$i],$a->[$i]);
		$is_computed[$i] = 0;
	}

	my($max_kkt_i) = -1;

	for($i=0;$i<$K;$i++)
	{
		$F[$i] = $b->[$i];
		$kkt[$i] = $F[$i];
		if($kkt[$i]>$max_kkt) { $max_kkt = $kkt[$i]; $max_kkt_i = $i; }
	}

	my($iter) = 0;
	my($diff_alpha) = 0;
	my($try_alpha) = 0;
	my($add_alpha) = 0;


	while($max_kkt >= $eps && $iter<$max_iter)
	{
		if($A[$max_kkt_i][$max_kkt_i] <= $zero)
		{
			$diff_alpha = 0.0
		}	
		else
		{
			$diff_alpha = $F[$max_kkt_i]/$A[$max_kkt_i][$max_kkt_i];
		}

		$try_alpha = $alpha[$max_kkt_i] + $diff_alpha;
		$add_alpha = 0.0;

		if($try_alpha < 0.0)
		{
			$add_alpha = -1.0 * $alpha[$max_kkt_i];
		}
		else
		{
			$add_alpha = $diff_alpha;
		}

		$alpha[$max_kkt_i] = $alpha[$max_kkt_i] + $add_alpha;

		if(!($is_computed[$max_kkt_i]))
		{
			for($i=0;$i<$K;$i++)
			{
				$A[$i][$max_kkt_i] = Features::dotProduct($a->[$i],$a->[$max_kkt_i]);
				$is_computed[$max_kkt_i] = 1;
			}
		}
		
		for($i=0;$i<$K;$i++)
		{
			$F[$i] -= $add_alpha * $A[$i][$max_kkt_i];
			$kkt[$i] = $F[$i];
			if($alpha[$i] > $zero)
			{
				if($F[$i]<0)
				{ $kkt[$i] = -$F[$i]; }
				else
				{ $kkt[$i] = $F[$i]; }
			}
		}

		$max_kkt = -100000;
		$max_kkt_i = -1;
		
		for($i=0;$i<$K;$i++)
		{
			if($kkt[$i] > $max_kkt)
			{ $max_kkt = $kkt[$i]; $max_kkt_i = $i; }	
		}

		$iter ++; 
	}

	return @alpha;
}

sub train {

	my($corpus) = shift;
	my($Parameters) = shift;
	my($dictFile) = shift;
	my($numDict) = shift;
	my $senNum;

	my($AvgParams) = new Parameters;
	my($updatedParams);

	my($prevclassacc)=-1;
	my($currclassacc);
	local($numUpdates) = 0;
	local($numFailures) = 0;
	local($numCopied) = 0;
	local($totalNodes) = 0;

	my($i,$j);
	my($newK);


	for($i=$C{'prevIter'};$i<$C{'targetIter'};$i++)
	{
		my($TempParams) = new Parameters;

		foreach $senNum (sort {$a<=>$b} keys %$corpus) {

			if($C{'senTrain'} < $senNum) { 
				last; 
			}

			print STDERR "Iteration $i SenId $senNum SenNum $senNum/$C{'senTrain'}\n";

			# print STDERR "Predicting and Updating parameters $senNum\n";
			if($C{'trainAlgo'}==1) {
				$newK = $corpus->predictAndupdate1($senNum,$Parameters,1);
			}
			elsif($C{'trainAlgo'}==2) {
				$newK = $corpus->predictAndupdate2($senNum,$Parameters,1);
			}
			elsif($C{'trainAlgo'}==3) {
				$newK = $corpus->predictAndupdate3($senNum,$Parameters,1);
			}
			elsif($C{'trainAlgo'}==4) {
				$newK = $corpus->trainAlgo4($senNum,$Parameters,1);
			}
			elsif($C{'trainAlgo'}==5) {
				$newK = $corpus->trainAlgo5($senNum,$Parameters,1);
			}

			$AvgParams->addparams($Parameters);

		}	


		# Store the parameters which have not been averaged yet
		# print STDERR "Storing Parameter Values in a File\n";
		$AvgParams->store("UnavgModelPars/$C{'paramFileUAvgOut'}.$i.temp");

		$TempParams->copy($AvgParams);
#		$TempParams->average(($i+1)*(50));
		$TempParams->average(($i+1)*(scalar(keys %$corpus)));
		$TempParams->store("AvgModelPars/$C{'paramFileOut'}.$C{'K'}.".eval($i+1));

		print "!!!!!!!!!!!!!!END OF ITERATION ($numUpdates,$numFailures,$numCopied,$totalNodes)!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!\n";
		$numUpdates = 0;
		$numFailures = 0;
		$numCopied = 0;
		$totalNodes = 0;

	}

	$AvgParams->store($C{'paramFileUAvgOut'});

	#$AvgParams->average($C{'targetIter'}*(scalar(keys %$corpus)));
	$AvgParams->average($C{'targetIter'}*($C{'senTrain'}));
	$AvgParams->store($C{'paramFileOut'});

#	$corpus->getDecoderLists($Parameters,$dictFile,$numDict,1);

}

sub test {
	my($corpus) = shift;
	my($Parameters) = shift;
	my($dictFile) = shift;
	my($numDict) = shift;
	
	my($K) = shift;
	my($newK);

	my($i,$j,$t);
	my($nFeatures);

	foreach $senNum (sort {$a<=>$b} keys %$corpus) {

		if($C{'senTest'} < $senNum) { 
			last; 
		}

		print STDERR "Testing:",$senNum,"\n";

		if($C{'testAlgo'}==2) {
			$newK = $corpus->predictAndupdate2($senNum,$Parameters,0);
		}
		elsif($C{'testAlgo'}==1) {
			$newK = $corpus->predictAndupdate1($senNum,$Parameters,0);
		}
		elsif($C{'testAlgo'}==3) {
			$newK = $corpus->predictAndupdate3($senNum,$Parameters,0);
		}
		elsif($C{'testAlgo'}==4) {
			$newK = $corpus->testAlgo4($senNum,$Parameters,0);
		}
		elsif($C{'testAlgo'}==5) {
			$newK = $corpus->testAlgo5($senNum,$Parameters,0);
		}

#		print $senNum."\n";
#		$corpus->{$senNum}->{'AlignBeam'}->[0]->print($corpus->{$senNum}->{'SSen'});

	}


}

sub decodeText {
	my($corpus) = shift;
	my($Parameters) = shift;
	
	my($K) = shift;
	my($newK);

	my($i,$j,$t);
	my($nFeatures);

	foreach $senNum (sort {$a<=>$b} keys %$corpus) {
		print STDERR "Decoding:--",$senNum,"--\n";
		#print "Decoding:---------------",$senNum,"---------------\n";

		$newK = $corpus->decodeBottomUp($senNum,$Parameters);

		#$corpus->printTgt($senNum);
	}

}

sub printAlns {
	my($corpus) = shift;
	my($senNum) = shift;
	my($engsen);
	my($i,$k);

	$engsen = $corpus->{$senNum}->{'SSen'};

	my($predictAln) = $corpus->{$senNum}->{'AlignBeam'}->[0];

	for($i=0;$i<@{$engsen};$i++) {
		foreach $k (@{$predictAln->{'aln'}->[$i]}) {
			print "$senNum\t$i\t$k\n";
		}
	}

	while(@{$corpus->{$senNum}->{'AlignBeam'}}>1) {
		my $ele = pop(@{$corpus->{$senNum}->{'AlignBeam'}});
	}
}

sub printparallel {
	my($this) = shift;  # Of type $this->[$j]
	my($i,$j,$k);
	$j=shift;
	my($K) = shift;
	my($engsen);
	#print "---------\n";
	#for($j=0;$j<=$#$this;$j++)  
	#{
		#print "SenNum = $j "..$this->[$j]->{'SenNum'}."\n";
		$engsen = $this->[$j]->{'SSen'};
		for($i=0;$i<=$#{$engsen->{'word'}};$i++)
		{

			#if($i<=9) { print STDERR "0"; }
			print STDERR "$i => ";
			#if($this->[$j]->{'Align'}->{'aln'}->[$i] eq "-")
			#{ print STDERR "-"; }
			#elsif($this->[$j]->{'Align'}->{'aln'}->[$i]<=9)
			#{ print STDERR "0"; }
#			print STDERR $this->[$j]->{'Align'}->{'aln'}->[$i]."\t";
			my(%variations);
			for($k=0;$k<$K;$k++)
			{
			
				#print STDERR "\t";
				#if($this->[$j]->{'AlignBeam'}->[$k]->{'aln'}->[$i] eq "-")
				#{ print STDERR "-"; }
				#elsif($this->[$j]->{'AlignBeam'}->[$k]->{'aln'}->[$i]<=9)
				#{ print STDERR "0"; }
				#print STDERR $this->[$j]->{'AlignBeam'}->[$k]->{'aln'}->[$i]."/".&r($this->[$j]->{'AlignBeam'}->[$k]->{'alnscr'}->[$i],1); 

				$var = $this->[$j]->{'AlignBeam'}->[$k]->{'aln'}->[$i]."/".&r($this->[$j]->{'AlignBeam'}->[$k]->{'alnscr'}->[$i],1);
				if($k==0) { $var="*".$var; $variations{$var}=1; }
				elsif(!($variations{"*".$var}))
				{ $variations{$var} = 1; }
			}
			$varstr = "";
			foreach $var (sort {$a <=> $b} keys %variations)
			{	
				$varstr .= $var." ";
			}
#			print STDERR $varstr;
			print STDERR "\n";
			undef($variations)
	
		}	
		#print STDERR "Scr => .";
		#for($k=0;$k<$K;$k++)
		#{
		#	print STDERR "\t   ".&r($this->[$j]->{'AlignBeam'}->[$k]->{'score'},1);
		#}
		print STDERR "\n---------\n\n";
	#}
}

sub getAccuracy {
	my($this) = shift;
	my($total) = 0;
	my($correct) = 0;
	my($a,$b);

	for($j=0;$j<=$#$this;$j++)  
	{
		($a,$b) = $this->[$j]->{'Align'}->getCorrects($this->[$j]->{'AlignBeam'}->[0]);
		$total+=$b;
		$correct+=$a;	
	}	

	return $correct*100/$total;
}

sub r {
    my ($number,$decimals) = @_;
    return substr($number+("0."."0"x$decimals."5"),
                  0, $decimals+length(int($number))+1);
}

1;
